6 Graph Structure Analysis
A depth-first search can be used to preprocess a graph or it can be directly embedded in a more complex algorithm. In the latter case, the action taken when a vertex is visited depends on the algorithm in which the search is embedded. In the former case, the normal objective of the search is to gather information about the structure of the graph (as seen from the vantage point of the search).
The depth-first labeling is the order in which was visited during the search. Depth-first numbers range from to . The root is mapped to one.
The predecessor (or parent) mapping identifies the vertex from which was discovered during the search. The root has no parent.
The depth mapping is the length of the path from to its root in the depth-first spanning tree of .
Subsequent sections provide algorithmic examples of structural information about a graph that is obtained by making small alterations to the depth-first search and depth-first traversal algorithms.