Cycle Detection in Graphs

What is this?

A cycle is a loop — a path that wanders away from a starting point and eventually circles right back to it. Sometimes loops are fine, but often they mean disaster: a to-do list where task A waits on task B, B waits on C, and C waits on A can never get started. Cycle detection is how you spot these loops before they cause a deadlock. The one decision that drives everything is whether your connections are two-way streets or one-way streets, because each needs a different detective technique.

💡 Fun fact: databases hunt for cycles every day. When transactions wait on each other in a ring — A holds a row B wants, B holds a row A wants — the system has a deadlock. The database builds a "wait-for graph," finds the directed cycle, and kills one transaction (the "victim") to break the loop so the rest can proceed.

🔓 The problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: a cycle is a path that loops back onto itself, and finding one is the difference between "this can be ordered/resolved/executed" and "this deadlocks forever." The whole chapter rests on one fork in the road: is the graph undirected (use Union-Find or DFS-with-parent) or directed (use DFS recursion-stack coloring or Kahn's topological sort)? Pick the wrong tool for the wrong graph and you'll get the wrong answer with confident-looking code.

1. What cycle detection really means

A cycle is a path that starts and ends at the same vertex without reusing an edge. Detecting one tells you a graph can't be safely linearized — no valid ordering, possible deadlock, infinite loop. The catch is that "what counts as a cycle" depends entirely on whether edges have direction:

The crucial split:

• Undirected graphs. Walking a—b then back b—a is not a cycle — it's the same edge. A real cycle means reaching an already-visited node through a different edge. Tools: Union-Find (two endpoints already in the same set ⇒ this edge closes a loop) or DFS that ignores the parent you came from.
• Directed graphs. Direction matters: a cycle is a back-edge that points to a node still sitting on your current recursion path. Tools: DFS with white/gray/black coloring (a recursion-stack check) or Kahn's topological sort (nodes left unprocessed ⇒ cycle).

Using an undirected technique on a directed graph is the classic disaster — see the pitfalls below.

2. Where you'll actually meet this

Cycle detection is a workhorse of systems and infrastructure:

• Deadlock detection (distributed systems & databases). A wait-for graph of who-holds-what / who-wants-what deadlocks exactly when it has a directed cycle. Databases detect it, then abort a victim transaction.
• Dependency cycles. Build tools (Make, Bazel, Gradle) and package managers (pip, npm, Cargo) topo-sort dependencies; a cycle is an unsatisfiable, hard error.
• Garbage collection. Reference-counting GCs leak on reference cycles; cycle collectors exist precisely to find and reclaim them.
• Spreadsheets & dataflow engines. Circular formula references are directed cycles flagged before evaluation.
• Networking & finance. Routing-loop prevention; arbitrage = a profitable cycle in a currency graph; fraud rings = suspicious cycles in transaction graphs.

If a problem says circular dependency, deadlock, prerequisites, "is this a valid ordering," reference cycle — you're in this chapter.

3. The cycle-detection toolkit

Choose by graph type first, then by what else you need:

1. Undirected — Union-Find (disjoint set). Process edges one at a time. If both endpoints already share a root, this edge forms a cycle. Near-O(E·α(V)), no traversal needed, perfect for streaming edges. (detail below.)
2. Undirected — DFS with parent-skip. DFS the graph; if you reach an already-visited neighbor that isn't the node you came from, that's a cycle. O(V+E).
3. Directed — DFS 3-color / recursion-stack. Color white (unseen) → gray (on current path) → black (done). Stepping onto a gray node = a back-edge = a cycle. O(V+E), early-exits the instant a cycle appears.
4. Directed — Kahn's topological sort. Repeatedly remove indegree-0 nodes. If you can't remove all of them, the leftovers form a cycle. O(V+E), iterative (no recursion depth risk), and yields a topological order for free.

Rule of thumb: undirected ⇒ Union-Find when edges arrive one-by-one, DFS-parent when you already have the graph. Directed ⇒ DFS-color for shortest code and early exit, Kahn when you also want the ordering.

4. A 30-second worked example (catch a back-edge)

Directed graph a → b → c → a. Run DFS from a, coloring as you go:

The edge c → a points at a node still gray (still on the active recursion path), which is exactly the signature of a cycle. Had a been black (fully finished) instead, that same edge would be harmless — a cross/forward edge, not a loop. That gray-vs-black distinction is the entire trick of directed cycle detection.

5. Problems in this chapter

▶ Course Schedule

Decide whether all tasks can be finished given "B before A" prerequisites — i.e. is the dependency graph a DAG? Build a directed graph, then either DFS with white/gray/black coloring (back-edge ⇒ cycle) or Kahn's indegree BFS (leftover nodes ⇒ cycle). The answer is "finishable ⟺ acyclic ⟺ a topological order exists."
Pattern: directed cycle detection / topological sort. Target: O(V + E) time, O(V + E) space.

6. Common pitfalls 🚫

• Using an undirected technique on a directed graph (or vice versa). Union-Find and "ignore the parent" only make sense without direction. On a directed graph you must track the recursion stack (gray nodes) or use Kahn — otherwise you'll miss cycles or hallucinate them.
• Confusing "visited" with "on the current path." A node already fully explored (black) is fine to revisit; only a node still on the active path (gray) signals a cycle. Collapsing those two states is the most common directed-cycle bug.
• Wrong edge direction. "A depends on B" must become a consistent edge convention (e.g. B → A). Reverse it and your topo sort / cycle check answers a different question.
• Forgetting disconnected components. Start a fresh DFS / seed Kahn from every unvisited node, not just node 0 — a cycle can hide in a component you never entered.
• Ignoring self-loops. [x, x] is a length-1 cycle; make sure your check flags it.
• Deep recursion on long chains. Recursive DFS can blow the stack on a pathological chain — prefer Kahn (iterative) when V is large.

7. Key takeaways

1. Decide undirected vs directed before writing a line. That single choice dictates the entire algorithm; mixing them is the headline mistake.
2. Undirected: Union-Find (same set ⇒ cycle) for streamed edges, or DFS that skips the parent for a held graph.
3. Directed: DFS with white/gray/black — a back-edge into a gray node is a cycle — or Kahn's indegree BFS, where leftover nodes ⇒ cycle and you also get a topological order.
4. Directed acyclic ⟺ a topological order exists, which is why cycle detection and topo sort are two views of the same question.
5. All these run in O(V+E); cover every component, handle self-loops, and watch recursion depth.
6. It powers real infrastructure — deadlock detection, dependency resolution, GC reference cycles — which is exactly why interviewers reach for it.