====== Section 3.2 Graph Connectivity and Traversal ======

Breadth-First Search is a method of search through a graph to assemble the connected component. It does this by adding a "layer," or the set of nodes connected to the root node //s//, and then recursively calling itself on each node in the layer. A few interesting properties of the breadth-first search and its resultant tree are that for any nodes //x// and //y// in layers L<sub>i</sub> and L<sub>j</sub> joined by an edge (x,y), i and j can differ by at most 1. Additionally, the nodes returned by a BFS started at node //n// are precisely those in the connected component of the graph containing //n//. 

The Depth-First Search is another method for finding all the nodes reachable from the starting node. Instead of visiting all the nodes layer by layer, however, this algorithm follows edges to unexplored nodes along one path until it reaches a dead end, at which point it will backtrack through all of its explored nodes until it finds one with an edge to an unexplored node. Now it will take that advance along the unexplored nodes in that direction until it again reaches a dead end and has to repeat the process. The algorithm will continue this until all the nodes are visited. As opposed to a Breadth-First Search where all the nodes connected by an edge must be no more than one layer apart, the Depth-First search can create trees with whose nodes are separated by more than one edge, but one of these must be a descendant of the other. 

Qualitatively, these two algorithms will have roughly the same running times and efficiency since they will both be traversing the same number of nodes and edges. This is due to the fact that for two nodes in a graph, their connected components are either completely identical or disjoint (KT p. 86). 

I found this chapter easily readable although a few of the proofs took a few minutes of digestion to fully comprehend.