# 6.3 Cycle Detection

It can be shown that each back edge detected during a depth-first search of the graph $G=(V,E)$ corresponds to a cycle in $G$. Recall from Section 5.3 that a back edge connects a vertex to one of its ancestors in the spanning tree.

A minor modification of the depth-first search will produce a test for cycles. We will examine the case of cycle detection in undirected graphs first. It is simpler.

## 6.3.1 Detecting Cycles in Undirected Graphs

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

Algorithm 11: Cycle Detection in Undirected Graphs
 next edge for all vertices $w$ adjacent to $v$ if evaluate($\gamma,w$) is $unvisited$ $depth=depth+1$ visit($w,v$) $v=w$ else cycle detected goto next edge

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

## 6.3.2 Detecting Cycles in Directed Graphs

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.

Algorithm 12: Cycle Detection in Directed Graphs
 next edge for all vertices $w$ adjacent to $v$ if evaluate($\gamma,w$) is $unvisited$ $depth=depth+1$ visit($w,v$) $v=w$ else if evaluate($\gamma,v$)$>$evaluate($\gamma,w$) and evaluate($\gamma,r$)$<$evaluate($\gamma,w$) cycle detected goto next edge

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