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.

A non-tree edge $(u,v)$ of the digraph can be of one of the following types:

• If $u$ is an ancestor of $v$, $(u,v)$ is a forward-edge.
• If $u$ is a descendant of $v$, $(u,v)$ is a back-edge.
• If neither of $u$ or $v$ are each other’s ancestor or descendant, then $(u,v)$ is said to be a cross-edge.

The solid lines in the figure above show some tree-edges. In each example, the dotted edge represents a non-tree edge.

Let’s see how we can go about classifying the edges of a directed graph during depth-first search.

Time tracking

The first thing we want to do is to track the order in which each vertex is visited and the order in which it is marked explored.

To accomplish this, we keep a global variable called $tick$, that’s initialized to $0$ and represents where we are in the timeline.

To maintain $tick$ ...