====== 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.

===== Breadth-First Search =====
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//.

===== Depth-First Search =====
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.