**__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.