6.3 Cycle Detection

Algorithm 11 implements a cycle test for undirected graphs that is illustrated on a fragment of Algorithm 6, the non-recursive dfs procedure.

Since the cycle test is an $O(1)$ operation, it does not increase the complexity of the depth-first search.

Testing for cycles in directed graphs is still a matter of looking for back edges. However, the process is complicated by the fact that the edges of a digraph that are not part of its spanning forest are not necessarily back edges either. The following observations permit the forward edges, cross edges, and back edges of a depth-first search to be distinguished efficiently.

It can be shown that the forward edges of a depth-first search connect vertices with low depth-first numbers to vertices with high depth-first numbers. Therefore, an edge $(v,w)$ of $G$ that is not part of its spanning forest is a forward edge when $\gamma(v)<\gamma(w)$.

Conversely, $(v,w)$ is a back edge or cross edge of $G$ when $\gamma(v)>\gamma(w)$.

Distinguishing between back edges and cross edges relies on the observation that a cross edge connects the current spanning tree to a spanning tree that was explored at an earlier stage of a depth-first traversal. Since the root $r$ of the current spanning tree must have a larger depth-first number than any vertex in any previously processed tree in the spanning forest, the condition $\gamma(r)>\gamma(w)$ must hold for a cross edge $(v,w)$.

Therefore, an edge $(v,w)$ of $G$ that is not part of its spanning forest is a back edge when the following conditions apply: $\gamma(v)>\gamma(w)$ and $\gamma(r)<\gamma(w)$.

This observation leads to Algorithm 12 for detecting cycles in a directed graph, it is a modification to Algorithm 6, the non-recursive depth-first search.

Obviously, the cycle test does not increase the complexity of the algorithm.