Graphs/Cycles

Notes

Detecting Cycles

Cycles can exist and be detected on either directed or undirected graphs.

For both types of graphs, a cycle exists if and only if there is a back edge on the graph. To detect a cycle, then, requires a depth-first search (see Graphs/DFS) and marking any back edges. If there are any back edges, the cycle exists.

Algorithm

To algorithmically find a back edge, we should consider undirected and directed graphs separately.

Detecting Cycles on Undirected Graphs

This is the easier case - each edge can be classified as either an edge that is part of the DFS tree, or a back edge. (There are no cross-edges in an undirected graph.)

To classify each edge, when visiting a vertex u, iterate through each edge that is incident to the vertex. If the opposite vertex has already been visited, the edge is a back edge. Otherwise, the edge is a DFS tree edge.

Detecting Cycles on Directed Graphs

For directed graphs, when visiting a vertex u, iterate through each outgoing edge that is incident to the vertex. If the opposite vertex has already been visited, we must determine if it is an ancestor of the current vertex (making it a back edge, and forming a cycle), or whether it is a cross edge (which connects to a vertex that is neither an ancestor nor a descendant, and not forming a cycle).

To do this, additional bookkeeping is needed for the DFS. The DFS must keep track of the vertices that are actively a part of the current recursive DFS call.