# 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.

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.

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.