Graphs record relationships. Nodes are connected to one another by edges. In a directed graph, the order of nodes connected by edges is not interchangeable, but rather they are ordered pairs. If a graph does not specify direction, we assume that it is not directed. Examples of graphs in real life include computer networks, social networks, transportation networks, information networks like the world wide web, and dependency networks which capture the inter-dependencies between components of a system(ie: a food web in nature). In non directed graphs, a path is a sequence of connected nodes. Simple paths contain no repetition of vertices. Cycles are like paths but the first node must be the same as the last and there can be no repetitions. An undirected graph is connected if there is a path between each pair of nodes. It is strongly connected if there is a path between each pair of nodes in both “directions”. Distance between two nodes is the number of nodes in the shortest path between them. A graph is a tree if it is connected and does not contain a cycle. Review: one node in a tree(often the smallest, no parents) is the root, descendants of nodes are children and nodes with children are their parents. Trees imply the concept of hierarchy. Each tree has exactly n-1 edges where n is the number of nodes. This is because the root has no edges and each addition adds one node and only one additional edge. Overall, this section is a solid 8/10. Very nice read.

The s-t connectivity problem us finding if there is a path between nodes s and t in a graph. This challenge resembles solving a maze. One approach to finding a solution is breadth first search. In breadth first search, we start at a “root” node s. We then search all nodes connected to it (first layer). Then, we search all nodes connected to those nodes in the first layer(second layer). We repeat until there are no nodes remaining. The number of a layer Li corresponds to its path distance from s. Because they are in layers, searches correspond to a tree like structure called a breadth-first search tree. Only edges which connect to a new node are included in the tree(no two edges to the same node in the next layer). Nodes will not be searched if there is no path between them ans s. Thus, the set R of searched nodes is the connected component of the graph containing s. If t is in R, there is a path and vice versa. Another tactic for solving the problem is depth-first search. This is a recursive approach. For depth-first search, we start at s and then search one connected node a, then search a connected node of b, etc, until we reach a node without a connection to a non-searched node. Then, we backtrack until we find a node with unexplored edges. We must maintain a copy of the nodes which we can backtrack to. Depth first search ultimately produces the exact same connected component as breadth first search. However, its tree representation looks very different from breadth first as seen in class. This is called a depth-first search tree. If a pair of nodes (a, b) are directly connected in the breadth first search tree of a graph then one is the ancestor of the other in the corresponding depth first search tree. The connected components of two nodes in a graph are either identical or have no nodes in common. This property holds for all graphs. Thus, to find all connected components of a graph we could find one connected component R and then only find the connected components of nodes not in R. This section was interesting, complex and very well articulated by the book. I would give it a solid 8/10 for readability.