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 γv\gamma(v) is the order in which vv was visited during the search. Depth-first numbers range from 11 to V|V|. The root is mapped to one.

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

  • The depth mapping δv\delta(v) is the length of the path from vv to its root in the depth-first spanning tree of GG.

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.

Additional Aspects Graph Structure Analysis