Edge Types
With DFS traversal of Graph, only some edges will be traversed. These edges will form a tree, called the depth-first-search tree starting at the given root, and the edges in this tree are called tree edges.
We can classify the various edges of the graph based on the color of the node reached when DFS follows the edge. Classification of the edges depends on what node we start from and in what order the algorithm happens to select successors to visit. Edges of graph can be divided into below categories:
- Tree edge belong to the spanning tree.
- Back edge point from a node to one of its ancestors in the DFS tree.
- Forward edge point from a node to one of its descendants.
- Cross edge point from a node to a previously visited node that is neither an ancestor nor a descendant.
Example
When the destination node of a followed edge is white, this is when the algorithm performs a recursive call. These edges are called tree edges. Tree edges also show the precise sequence of recursive calls performed during the traversal.
When the destination of the followed edge is gray, it is a back edge, shown in red. Because there is only a single path of gray nodes, a back edge is looping back to an earlier gray node, creating a cycle. A graph has a cycle if and only if it contains a back edge when traversed from some node.
When the destination of the followed edge is colored black, it is a forward edge or a cross edge. If there is a path from the source node to the destination node through tree edges, it is a forward edge. Otherwise, it is a cross edge.
