Cycle Detection
A cycle in a graph is a closed path that starts and ends at the same vertex. Cycle detection is a fundamental graph algorithm with wide practical applications — from identifying deadlocks in operating systems to validating dependency graphs in package managers.
What Is a Cycle?#
In the first diagram, every pair of vertices is connected by exactly one path — this is a tree, which is always cycle-free. In the second, vertices B and C are each reachable from A by two distinct paths, forming a cycle: A → B → C → A (equivalently, A → C → B → A going the other way).
Why Detect Cycles?#
| Application | Why Cycles Matter |
|---|---|
| Deadlock Detection | Processes waiting in a cycle = deadlock |
| Dependency Resolution | Circular dependencies are invalid (npm, pip) |
| Course Prerequisites | Circular prerequisites are impossible |
| Compiler Optimization | Loops in control flow graphs |
| Garbage Collection | Reference cycles need special handling |
| Topological Sort | Only possible on acyclic graphs (DAGs) |
Cycle Detection: Undirected vs Directed#
The two graph types require fundamentally different strategies. In an undirected graph, edges have no direction — any path you traverse is reversible, so any revisited vertex (other than the one you immediately came from) signals a cycle. In a directed graph, direction matters: reaching a previously visited vertex is sometimes perfectly valid because multiple directed paths can legitimately converge on the same destination. A cycle only exists if the edge leads back into the current active path, not just any vertex seen before. This difference demands a more precise tracking mechanism for directed graphs:
| Graph Type | Key Insight | Approach |
|---|---|---|
| Undirected | Finding a visited vertex that is not the parent indicates a cycle | DFS with parent tracking |
| Directed | Finding an edge to a vertex currently in the recursion stack indicates a cycle | DFS with color marking (white/gray/black) |
Cycle Detection in Undirected Graphs#
In an undirected graph, a cycle is present when DFS encounters an already-visited vertex that is not the direct parent of the current vertex. The reasoning is straightforward: if a neighbor is already visited and it is not the vertex we came from, then there must be at least two distinct paths connecting them — one through the DFS tree we have been building, and one through the edge we just found. Two paths between the same pair of vertices in an undirected graph always form a cycle.
Why Track Parent?#
In an undirected graph, every edge A—B is stored in both directions: A's adjacency list contains B, and B's adjacency list contains A. Without parent tracking, DFS would report a cycle every time it looks back at the vertex it just came from — producing a false positive on every single edge.
Cycle Detection in Undirected Graph
Detect if an undirected graph contains a cycle using DFS with parent tracking
Cycle Detection in Directed Graphs#
Directed graphs require a more nuanced approach. In a directed graph, it is perfectly normal to reach a vertex that was already visited in an earlier DFS branch — multiple directed paths can legitimately converge on the same destination. Reaching a previously visited vertex does not always indicate a cycle; the edge could be a forward edge or a cross edge, neither of which forms a cycle. What matters is detecting back edges: edges that point to a vertex that is still on the current recursion stack, meaning the path has looped back into itself.
The Three Colors#
| Color | State | Meaning |
|---|---|---|
| WHITE | Unvisited | Vertex hasn't been explored yet |
| GRAY | In Progress | Vertex is in current DFS path (recursion stack) |
| BLACK | Completed | Vertex and all descendants fully explored |
Two states — visited and unvisited — are not sufficient for directed graphs. A "visited" vertex might have been fully processed in an earlier, unrelated DFS branch, which is not a cycle. The GRAY state is what allows us to distinguish "currently on the active path" from "already finished elsewhere." Only an edge into a GRAY vertex closes a loop in the active path.
Key insight: A cycle exists precisely when DFS encounters an edge leading to a GRAY vertex — a back edge that closes a loop within the current DFS path.
Cycle Detection in Directed Graph
Detect if a directed graph contains a cycle using DFS with color marking
Alternative: Union-Find for Undirected Graphs#
For undirected graphs, Union-Find (Disjoint Set Union) offers a clean alternative to DFS. The idea is to process edges one at a time: if both endpoints already belong to the same connected component, adding the new edge would create a cycle. Note that Union-Find only applies to undirected graphs — it has no concept of edge direction and cannot detect directed cycles.
Cycle Detection with Union-Find
Detect cycles in undirected graphs using Disjoint Set Union
Comparison of Approaches#
α(V) is the inverse Ackermann function, nearly constant
| Approach | Graph Type | Time | Space | Best For |
|---|---|---|---|---|
| DFS with Parent | Undirected | O(V + E) | O(V) | General undirected graphs |
| DFS with Colors | Directed | O(V + E) | O(V) | General directed graphs |
| Union-Find | Undirected | O(E × α(V)) | O(V) | Edge-list representation |
Edge Classification in Directed Graphs#
DFS on a directed graph produces four distinct edge types. Understanding them clarifies why only one type — the back edge — signals a cycle:
| Edge Type | From → To | Detection | Indicates Cycle? |
|---|---|---|---|
| Tree Edge | Parent → Child in DFS tree | Target is WHITE | No |
| Back Edge | Descendant → Ancestor | Target is GRAY | Yes! |
| Forward Edge | Ancestor → Descendant (non-tree) | Target is BLACK | No |
| Cross Edge | Between unrelated subtrees | Target is BLACK | No |
Reviewing AI-Generated Code#
A solid grasp of cycle detection helps you spot subtle errors in AI-generated code — mistakes that look plausible at a glance but fail on edge cases or when the algorithm is applied to the wrong graph type:
What to Verify#
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Graph Type | Use different algorithms for directed vs undirected graphs | Using parent tracking for directed graphs |
| Parent Tracking | Skip parent in undirected cycle check | False positive: treating parent as cycle |
| Color Marking | An edge from the current vertex to a GRAY neighbor signals a cycle | Only checking visited, not in-progress (GRAY vs BLACK distinction missed) |
| All Components | Check all vertices for disconnected graphs | Only checking from one start vertex |
| Edge to Self | Self-loops are cycles if they matter | Not handling self-loops |
Common AI Pitfalls#
Cycle Detection Bugs
Common mistakes AI makes in cycle detection
Questions to Ask AI#
When AI generates cycle detection code, probe it with targeted questions:
- Does this algorithm target directed or undirected graphs?
- Why use color marking instead of a simple visited set?
- How does this handle disconnected graphs?
- Can you extend this to return the actual cycle path, not just a boolean?
Summary#
| Concept | Key Takeaway |
|---|---|
| Cycle | Path that starts and ends at the same vertex |
| Undirected Detection | DFS with parent tracking — finding a visited non-parent vertex indicates a cycle |
| Directed Detection | DFS with colors — encountering a GRAY neighbor (one still on the current path) is a back edge and signals a cycle |
| Union-Find | Alternative for undirected graphs — adding an edge within the same component creates a cycle |
| Back Edge | Only type of edge that indicates a cycle in directed graphs |
| Applications | Deadlock detection, dependency validation, topological sort feasibility |
Cycle detection is a cornerstone of graph algorithm design. Mastering it unlocks a range of downstream capabilities: verifying that topological sort is applicable, validating dependency graphs, detecting deadlocks, and reasoning about control flow. The three techniques covered here — DFS with parent tracking, three-color marking, and Union-Find — each represent a distinct mental model. Knowing when and why to reach for each one is what separates a solid understanding of graphs from surface-level familiarity.