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.