Chapter 3.2: Graph Connectivity and Traversal

Given a graph G=(V,E) and two particular nodes s and t, how do we know if there is a path from s to t in G? If the graph is small, this problem can be solved naturally by inspection. However, for large graphs (with many nodes and edges), there are two natural algorithms for solving this problem.

With BFS, we explore outward from s in all possible directions, adding nodes one “layer” at a time. We start with s and add all nodes that are joined by an edge to s, the first layer. Then we add all nodes that are joined by an edge to a node in the first layer, the second layer. We continue this way until there are no new nodes encountered.

• Layer L_0 consists of s
• Layer L_1 consists of all nodes that are adjacent to s
• Assuming we have defined layers L_1,…,L_j, then the layer L_j+1 consists of all nodes that do not belong to an earlier layer and that have an edge to a node in layer L_j

Note that layer L_j is the set of all nodes at distance exactly j from s. A node fails to appear in any of the layers if and only if there is no path to it. So BFS is not only determining the nodes that s can reach, it is also computing the shortest paths to them. BFS also produces a tree T rooted at s; we call this tree a breadth-first search tree.

Suppose T is a breadth-first search tree. Let x and y be nodes in T belonging to layers L_i and L_j respectively, and let (x,y) be an edge of G. Then i and j differ by at most 1.

The set of nodes discovered by the BFS algorithm is precisely those reachable from the starting node s. Call this set R the connected component of G containing s. We can also build R in a more general way. Begin by defining R = {s}. Then, if we find an edge (u,v) where u is in R but v is not in R, we can add v to R. We can keep growing the set R until there are no more edges leading out of R. The set R produced at the end of the algorithm is precisely the connected component of G containing s.

With DFS, we start from a node s and try the first edge leading out of it, to a node v. We then follow the first edge leading out of v, and continue in this way until we reach a “dead end”– a node for which we have already explored all its neighbors. Then, we backtrack until we reach a node with an unexplored neighbor, and resume from there. The DFS will also yield a rooted tree T, but it will be very different (structurally) from the T produced by BFS. We will make s the root of the tree and make u the parent of v when u is responsible for the discovery of v. The resulting tree is called a depth-first search tree. When DFS(u) is called, all nodes that are marked “explored” between the invocation and end of the recursive call are descendants of u in T.

Suppose T be a depth-first search tree. Let x and y be nodes in T and let (x,y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.

NOTE: Both BFS and DFS build the connected component containing s.

For any two nodes s and t in a graph, their connected components are either identical or disjoint.