(^146) | Chapter 6: Graph Algorithms
Note that this path may not be the shortest possible path—in this case the path
has seven vertices <s,1,3,4,5,9,t>, while a shorter path of five vertices exists
<s,6,5,9,t>.*
Input/Output
Input
A graphG=(V,E) and a source vertexs∈V. The quantitynrepresents the number
of vertices inG.
Output
DEPTH-FIRSTSEARCHproduces three computed arrays.d[v]determines the
depth-first numbering of the counter whenvis first visited; it is the value of the
counter whendfs_visitis invoked.pred[v]determines the predecessor vertex of
vbased on the depth-first search ordering.f[v]determines the depth-first
numbering of the counter whenvis determined to be completely visited; it is the
value of the counter when control returns fromdfs_visit. If the original graph is
unconnected, then thepred[]values actually encode a depth-first forest of depth-
first tree search results. To find the roots of the trees in this forest, scanpred[]to
find verticesr whosepred[r] value is –1.
Figure 6-10. Computed d, f, and pred data for a sample undirected graph; vertices are
colored when counter reaches 18
- Here the notion of a “shortest path” refers to the number of decision points betweensandt.
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