The Algorithm Design Manual Second Edition

5.9.1

Finding Cycles

Back edges are the key to finding a cycle in an undirected graph. If there is no

back edge, all edges are tree edges, and no cycle exists in a tree. But any back edge

going from x to an ancestor y creates a cycle with the tree path from y to x. Such

a cycle is easy to find using dfs:

The correctness of this cycle detection algorithm depends upon processing each

undirected edge exactly once. Otherwise, a spurious two-vertex cycle (x, y, x) could

be composed from the two traversals of any single undirected edge. We use the

finished flag to terminate after finding the first cycle.