Depth-First Search | 145GraphAlgorithmsInitially, all vertices are colored white, and DEPTH-FIRSTSEARCHinvokesdfs_visit
on the source vertex,s.dfs_visit(u)colorsugray before recursively invoking
dfs_visiton all adjacent vertices ofuthat have not yet been visited (i.e., they are
colored white). Once these recursive calls have completed,ucan be colored black,
and the function returns. When the recursivedfs_visitfunction returns, DEPTH-
FIRSTSEARCHbacktracks to an earlier vertex in the search (indeed, to a vertex
that is colored gray), which may have an unvisited adjacent vertex that must be
explored.
For both directed and undirected graphs, DEPTH-FIRSTSEARCHinvestigates the
graph fromsuntil all vertices reachable fromsare visited. If there remain unvis-
ited vertices inGthat are not reachable froms,DEPTH-FIRSTSEARCHrandomly
selects one of them to be the new source vertex and it repeats. This process
continues until all vertices inG are visited.
During its execution, DEPTH-FIRSTSEARCHtraverses the edges of the graph,
computing information that reveals the inherent, complex structure of the graph.
DEPTH-FIRSTSEARCHmaintains a counter that is incremented when a vertex is
first visited (and colored gray) and when DEPTH-FIRSTSEARCHis done with the
vertex (and colored black). For each vertex, DEPTH-FIRSTSEARCH records:
pred[v]
The predecessor vertex that can be used to recover a path from the source
vertexs to the vertexv
discovered[v]
The value of the incrementing counter when DEPTH-FIRSTSEARCHfirst
encounters vertexv; abbreviated asd[v]
finished[v]
The value of the incrementing counter when DEPTH-FIRST SEARCHis
finished with vertexv; abbreviated asf[v]
The order in which vertices are visited will change the value of the counter, and so
will the order in which the neighbors of a vertex are listed. This computed infor-
mation is useful to a variety of algorithms built on DEPTH-FIRSTSEARCH,
including topological sort, identifying strongly connected components, and identi-
fying potential weak spots in a network. Given the graph in Figure 6-8 and
assuming that the neighbors of a vertex are listed in increasing numerical order,
the information computed during the search is shown in Figure 6-10. The vertices
of the graph show their color when the counter reaches 18, just when vertex 8 is
visited (line 2 ofdfs_visitin Figure 6-9). Some parts of the graph (i.e., the
vertices colored black) have been fully searched and will not be revisited. Note
that (a) white vertices have computedd[]>18 (since they have not been visited
yet); (b) black vertices have computedf[]≤18 since they have been fully
processed; and (c) gray vertices haved[]≤18 andf[]≥18 since they are currently
being recursively visited bydfs_visit.
DEPTH-FIRSTSEARCHhas no global awareness of the graph, and so it blindly
searches the vertices <5, 6, 7, 8>, even though these are in the wrong direction
from the target,t. Once DEPTH-FIRSTSEARCHcompletes, thepred[]values
can be used to generate a path from each vertex to the original source vertex,s.Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use