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