Edge Classification in Directed Graphs
Learn how to classify edges in a directed graph using depth-first search.
We'll cover the following
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.
Get hands-on with 1200+ tech skills courses.