3.2: Graph Connectivity and Graph Traversal
Breadth-First Search
Breadth-first search adds nodes one “layer” at a time.
For each j >= 1, layer L(j) produced by BFS consists of all nodes at distance exactly j from s. There is a path from s to t if and only if t appears in some layer.
BFS marks down the edges of only parent-children, but not child-child.
Exploring a Connected Component
The set of nodes discovered by the BFS algorithm is precisely those reachable from the starting node s. We will refer to this set R as the connected component of G containing s.
R will consist of nodes to which s has a path. Initially R = {s} While there is an edge (u,v) where u is in R and v is not in R add v to R
This set R produced is precisely the connected component of G containing s.
Depth-First Search
DFS explores a graph G by going as deeply as possible and only retreats when necessary.
DFS(u): Mark u as "Explored" and add u to R For each edge (u,v) incident to u If v is not marked "Explored" then Recursively invoke DFS(v)
The Set of All Connected Components
For any two nodes s and t in a graph, their connected components are either identical or disjoint.
This is important - look at p.85 for help with DFS. 9/10.