6 Graph Structure Analysis
A depthfirst 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 depthfirst labeling $\gamma(v)$ is the order in which $v$ was visited during the search. Depthfirst numbers range from $1$ to $V$. The root is mapped to one.

The predecessor (or parent) mapping $\rho(v)$ identifies the vertex from which $v$ was discovered during the search. The root has no parent.

The depth mapping $\delta(v)$ is the length of the path from $v$ to its root in the depthfirst spanning tree of $G$.
Subsequent sections provide algorithmic examples of structural information about a graph that is obtained by making small alterations to the depthfirst search and depthfirst traversal algorithms.