Depthfirst Search
Properties of depthfirst search
Depthfirst search yields valuable information about the structure of a graph. Perhaps the most basic property of depthfirst search is that the predecessor subgraph G_{π} does indeed form a forest of trees, since the structure of the depthfirst trees exactly mirrors the structure of recursive calls of DFSVISIT. That is, u = _{π}[v] if and only if DFSVISIT(v) was called during a search of u's adjacency list. Additionally, vertex v is a descendant of vertex u in the depthfirst forest if and only if v is discovered during the time in which u is gray.
Another important property of depthfirst search is that discovery and finishing times have parenthesis structure. If we represent the discovery of vertex u with a left parenthesis "(u" and represent its finishing by a right parenthesis "u)", then the history of discoveries and finishings makes a wellformed expression in the sense that the parentheses are properly nested. For example, the depthfirst search of Figure 22.5(a) corresponds to the parenthesization shown in Figure 22.5(b). Another way of stating the condition of parenthesis structure is given in the following theorem.
Figure 22.5: Properties of depthfirst search. (a) The result of a depthfirst search of a directed graph. Vertices are timestamped and edge types are indicated as in Figure 22.4. (b) Intervals for the discovery time and finishing time of each vertex correspond to the parenthesization shown. Each rectangle spans the interval given by the discovery and finishing times of the corresponding vertex. Tree edges are shown. If two intervals overlap, then one is nested within the other, and the vertex corresponding to the smaller interval is a descendant of the vertex corresponding to the larger. (c) The graph of part (a) redrawn with all tree and forward edges going down within a depthfirst tree and all back edges going up from a descendant to an ancestor.
Classification of edges: Another interesting property of depthfirst search is that the search can be used to classify the edges of the input graph G = (V, E). This edge classification can be used to glean important information about a graph.
We can define four edge types in terms of the depthfirst forest G_{π} produced by a depthfirst search on G.

Tree edges are edges in the depthfirst forest G_{π}. Edge (u, v) is a tree edge if v was first discovered by exploring edge (u, v).

Back edges are those edges (u, v) connecting a vertex u to an ancestor v in a depthfirst tree. Selfloops, which may occur in directed graphs, are considered to be back edges.

Forward edges are those nontree edges (u, v) connecting a vertex u to a descendant v in a depthfirst tree.

Cross edges are all other edges. They can go between vertices in the same depthfirst tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depthfirst trees.
In Figures 22.4 and 22.5, edges are labeled to indicate their type. Figure 22.5(c) also shows how the graph of Figure 22.5(a) can be redrawn so that all tree and forward edges head downward in a depthfirst tree and all back edges go up. Any graph can be redrawn in this fashion.
The DFS algorithm can be modified to classify edges as it encounters them. The key idea is that each edge (u, v) can be classified by the color of the vertex v that is reached when the edge is first explored (except that forward and cross edges are not distinguished):

WHITE indicates a tree edge,

GRAY indicates a back edge, and

BLACK indicates a forward or cross edge.
The first case is immediate from the specification of the algorithm. For the second case, observe that the gray vertices always form a linear chain of descendants corresponding to the stack of active DFSVISIT invocations; the number of gray vertices is one more than the depth in the depthfirst forest of the vertex most recently discovered. Exploration always proceeds from the deepest gray vertex, so an edge that reaches another gray vertex reaches an ancestor. The third case handles the remaining possibility; it can be shown that such an edge (u, v) is a forward edge if d[u] < d[v] and a cross edge if d[u] > d[v].
In an undirected graph, there may be some ambiguity in the type classification, since (u, v) and (v, u) are really the same edge. In such a case, the edge is classified as the first type in the classification list that applies. Equivalently, the edge is classified according to whichever of (u, v) or (v, u) is encountered first during the execution of the algorithm.
We now show that forward and cross edges never occur in a depthfirst search of an undirected graph.