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 visit | Depth 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.
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.