Cycle Detection
Scenario
You're writing a package manager that needs to install dependencies. Package A needs B, B needs C, and C needs A.
How do you detect this circular loop before your installer gets stuck in an infinite recursion?
Why it exists
Problem: A cycle in a graph represents a circular dependency or an infinite loop. Standard traversal algorithms can loop forever unless we explicitly detect cycles.
Naive approach: Just tracking a 'visited' set works for finding components, but it fails to distinguish a harmless converging path (cross-edge) from a true loop (back-edge) in directed graphs.
Better idea: The approach splits by directionality. For undirected graphs, we track the immediate parent to ignore the edge we just arrived on. For directed graphs, we track the active recursion stack to identify when a path bites its own tail.
Mental model
Imagine walking through a maze trailing a ball of string. A cycle is found if you bump into your own unbroken string (a node on your active path). Bumping into string you've already cut and left behind (a fully processed node) is just a cross-edge.
Cycle detection requires entirely different algorithms depending on graph directionality.
For undirected graphs, every edge goes both ways. If A goes to B, B goes back to A. To avoid falsely calling this a cycle, we pass the 'parent' in our DFS and skip it.
For directed graphs, a cycle only exists if a path loops back into itself. We use three states: Unvisited (White), Visiting (Gray, on the stack), and Visited (Black, done). A cycle is specifically a back-edge to a Gray node.
Repeated decision: Does this edge lead somewhere already on my current path?
Explanation
Cycle detection fundamentally changes based on whether the graph is **directed** or **undirected**.
### Undirected Graphs
In an undirected graph, an edge between A and B means you can travel A → B and B → A. If you run a standard DFS, the moment you visit B, its neighbor list contains A. If you just check if A is visited, you'll immediately claim a cycle exists! To fix this, you must pass the `parent` node into your DFS. If a neighbor is already visited, but it is *not* the parent you just came from, you have found a true cycle. (Note: an alternative way to detect undirected cycles is Union-Find, which is covered later).
Hand-trace (Undirected: 0-1, 1-2, 2-0):
1. Start DFS at 0 (parent: None). Mark 0 visited. Visit neighbor 1.
2. At 1 (parent: 0), neighbor 0 is visited, but it's the parent. Skip it. Visit neighbor 2.
3. At 2 (parent: 1), neighbor 0 is visited and is NOT the parent. Cycle detected!
### Directed Graphs
In a directed graph, tracking the parent isn't enough. Paths can converge without forming a cycle (a cross-edge). For example, A → B, A → C, B → C is a directed acyclic graph (DAG). If we DFS A → B → C, C is marked visited. When we backtrack to A and visit C directly, C is already visited. If we just check a single `visited` set, we'd falsely declare a cycle.
Instead, we track the **recursion stack**. Nodes have three states:
- **Unvisited (White)**: Never seen.
- **Visiting (Gray)**: On the current path (in the call stack).
- **Visited (Black)**: Fully processed and popped off the stack.
A cycle exists if and only if we see a back-edge to a **Gray** node. A visited Black node is just a re-reached finished node, not a cycle.
Hand-trace (Directed: A→B, B→C, A→C):
1. DFS A (Gray). Visit B (Gray).
2. From B, visit C (Gray). C has no neighbors. Mark C Black (Done).
3. Back to B. B has no other neighbors. Mark B Black.
4. Back to A. Next neighbor is C. C is Black. This is a cross-edge, not a cycle! Graph is acyclic.
Now, if we had C→A: When at C (Gray), its neighbor A is Gray! Cycle detected!
Key points
- Direction matters: Undirected and directed graphs use fundamentally different cycle detection logic. A directed cycle and an undirected cycle are NOT found the same way.
- Undirected: Track the Parent: In undirected graphs, skip the node you just came from. Any other visited node is a cycle.
- Directed: 3-Color State: In directed graphs, track the active recursion stack. A cycle is a back-edge to a node currently on the stack.
Pattern: 3-Color DFS / Parent Tracking
Recognition cues:
- You need to verify if a schedule or dependency tree is valid.
- The problem asks to find if an infinite loop exists in a network.
Failure signals
- A directed graph DFS throws false positives on cross-edges.
- A standard undirected DFS says every single edge is a cycle.
Engineering examples
Package Managers and Build Systems
Software dependencies often form complex graphs.
Build tools like Make, npm, and pip use directed cycle detection (often implicitly via Topological Sort) to abort if package dependencies form an unresolvable loop.
When not to use
- Finding the shortest cycle: DFS just finds *a* cycle, not necessarily the shortest one. Finding the shortest cycle requires BFS.
Common mistakes
- Using undirected cycle detection on a directed graph: If you just check if a neighbor is in a single 'visited' set, you will falsely flag cross-edges (independent paths that merge at a shared dependency) as cycles.
- Forgetting to remove from the recursion stack: In directed graphs, if you forget to mark a node as Black (fully visited) after its DFS completes, subsequent independent paths will see it as Gray and falsely think they hit a cycle.
Glossary
- back edge
- An edge that points to an ancestor node that is currently on the recursion stack.
- cross edge
- An edge that points to a node that has already been completely visited and popped off the recursion stack.
- parent node
- In an undirected graph DFS, the immediate node we just came from.
Recall questions
- Why does a standard DFS with a single visited set fail for cycle detection in directed graphs?
- How do we avoid falsely detecting the edge we just came from as a cycle in an undirected graph?
- In the 3-color directed cycle detection, what does it mean when a DFS encounters a 'Gray' (visiting) node?
Questions & answers
Determine if a course schedule is possible given prerequisite pairs.
Build a directed graph where A -> B means A is a prerequisite for B. Use 3-color DFS to detect cycles; if a cycle exists, the schedule is impossible.
Approach: This is the canonical directed cycle detection problem.
Detect if an undirected graph contains a cycle.
Run DFS while passing the parent node. If a visited neighbor is not the parent, a cycle exists.
Approach: Standard undirected cycle check, O(V+E).
Interesting facts
- The 3-color (White/Gray/Black) terminology comes directly from the classic algorithm textbook Introduction to Algorithms (CLRS).
Continue learning
Previous: DFS on Graphs
Next: Topological Sort
Related: DFS on Graphs
Related: Topological Sort
Related: Union-Find