Edge Classification in Directed Graphs

Edges of a directed graph are classified into four categories depending on when they are first explored during a depth-first search.

This classification of edges is easily done by making small changes to depth-first search and is surprisingly useful when designing other applications of depth-first search.

Classification of edges

The edges of a directed graph that become part of the depth-first tree or the depth-first forest are called tree-edges. The remaining non-tree edges are classified depending on the relationship between its end-vertices.