cycle detection

A cycle is a path that loops back to where it started without retracing a step — a round trip through the graph. Asking whether one exists is a basic and surprisingly useful question: a dependency graph with a cycle means tasks that wait on each other forever (a deadlock), a build system with a cycle cannot decide a compile order, and a graph with no cycle at all (a forest, or a DAG when directed) enjoys special, easier structure. Cycle detection is simply deciding whether the graph contains a cycle, and graph search answers it in linear time.

Depth-first search detects cycles by watching for one telltale edge. For an undirected graph: run DFS, and if you ever reach an already-visited vertex that is not the parent you came from, you have found a back edge, and a back edge closes a cycle (the tree path from that ancestor down to you, plus the back edge). The 'not the parent' clause matters because in an undirected graph the edge you just came along would otherwise look like a cycle of length two. For a directed graph the rule is sharper: a cycle exists exactly when DFS finds an edge to a vertex that is currently on the recursion stack (still being processed) — a so-called gray vertex. Reaching a vertex that is finished (already fully explored) is fine and signals no cycle; only an edge into something still open does. A clean alternative for directed graphs is to attempt a topological sort: it succeeds if and only if there is no cycle, and its failure pinpoints the cyclic part. All of these run in O(n + m).

Beyond yes/no, cycle detection underpins deadlock detection in operating systems and databases, validating that a dependency or build graph is acyclic, finding negative-weight cycles (with extra machinery), and confirming a graph is a tree or DAG before running algorithms that require it. Two honest cautions. First, the undirected and directed tests are genuinely different — the directed rule needs the on-stack (gray) check, and naively reusing the undirected 'visited but not parent' test on a directed graph reports false cycles. Second, for a special structured setting — detecting a cycle in a functional graph or a linked list, where each node has exactly one successor — there is a beautiful constant-space technique (Floyd's tortoise-and-hare two-pointer method) that does not need to store visited marks; but for a general graph, the DFS back-edge test is the standard tool.