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

Recall that Algorithms 5 and 6 gathered three bits of structural information as it proceeded:

• The depth-first labeling $\gamma(v)$ is the order in which $v$ was visited during the search. Depth-first 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 depth-first spanning tree of $G$.

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.