Reading

Unit 5 Notes Sections 1.1,1.2.

Quiz questions

A more careful depth-first search

In this section, we'll consider a slightly different version of depth-first search. We'll lose the "generic search" framework, but we'll gain a lot more information about the search. In particular, we'll get a closer connection to the underlying search tree, in which we'll explicitly see our search as doing a depth-first traversal of the underlying search tree:

The idea is this: in our previous search, a vertex was either "visited" or "unvisited", and that was it. Now we'll make three categories: unvisited, visit-in-progress, visit-complete, which we'll represent as the "colors" white, gray and black. First we'll phrase this recursively. "Depth first visit" plays the role of our search, and to complete the presentation in the same basic form as Cormen Leiserson and Rivest, we'll have a "driver" called "depth first search" that makes sure all vertices are eventually found.

Depth first visitDepth first search
DFSVisit(vertex u)
  color u gray
  for each neighbor v of u do
    if v is white
      DFSVisit(v)
  color u black
DFS(graph G)
  set the color of all vertices in G to white
  for each vertex u in G do
    if u is white
      DFSVisit(u)

We can make DFSVisit an iterative algorithm and see that it's got the Stack connection to our original formulation to depth-first-search as follows (Note: in [ ]'s is some optional bookkeeping that can be done while the search progresses. We'll talk more about what this additional bookkeeping does for you):

DFSVisit(vertex s)
initialize S to an empty stack of vertex-integer pairs
color s gray [ parent[s] = null; time++; d[u] = time; ]
S.push((s,1))
while S not empty do
  (u,k) = S.pop()
  if u has k or more neighbors
    S.push(u,k+1)
    v = u's kth neighbor
    if v's color is white
      color v gray [ parent[v] = u; time++; d[u] = time; ]
      S.push(v, 1)
  else
    color u black [ time++; f[u] = time; ]
	

Now we get this beautiful property that the stack S is precisely the path from root s down to the current vertex u in the search tree. Moreover, since only the vertices currently on the stack are colored gray, we can check in constant time whether a given vertex is "on the current path" by checking its color.

Properties

This version of depth-first search has some interesting properties.
  1. We still have the same concept of "search tree", and once again if we do the optional bookkeeping and keep track of the "parent" fields, that tree is explicit, i.e. we can recover it.
  2. The gray vertices are exactly he vertices on the stack, and the vertices on the stack, ordered from bottom to top, comprise a path, and this path is a path in the search tree.
  3. Consider the vertex v at line "v = u's kth neighbor". If v is colored white, then the descendents of v in the searchtree that is ultimately generated will be exactly the vertices reachable from v via paths consisting solely of vertices colored white. Moreover, all such vertices will be colored black before v gets colored black.

Finding cycles in graphs

One extremely important property of a graph is whether or not it contains cycles. Depth-first search gives us a beautiful way to determine whether or not a graph has cycles.

Theorem: Suppose DFS is run on directed graph G. G has cycles if and only if at some point vertex v at line "v = u's kth neighbor" has color gray. Proof: If $v$ is colored gray, then it is on the current stack, which means that there is a path from $v$ to $u$. Because this vertex is a "$v$" in the algorithm, there is an edge from $u$ to $v$, which completes the cycle. More interestingly, if there is a cycle in $G$, can we show that we must eventually have a "$v$" that's colored gray? Denote by $w$ the first vertex encountered by DFS that is a part of a cycle (i.e. all prior vertices encountered are not part of any cycle). Then any cycle involving $w$ consistes purely of vertices currently colored white. At least one such vertex must have an edge back to $w$ (otherwise $w$ would not be the first encountered vertex that's part of a cycle), denote such a vertex by $y$. $y$ is colored black before $w$, so $w$ is still gray when every one of the neighbors of $y$ is processed, including the point at which $w$ itself is processed as a neighbor, which means we will be at a point where $v$ from "v = u's kth neighbor" is colored gray.