Cycle Detection in Directed Graphs
Last Updated: April 5, 2026
Cycle detection in directed graphs is about identifying whether a sequence of edges leads back to the same node. This is a critical concept for problems involving dependencies, where a cycle makes tasks impossible to complete.
In this chapter, we will cover two approaches to detect cycles in directed graphs, understand why undirected techniques fail here, and solve two classic interview problems that test this concept.
What Is a Cycle in a Directed Graph?
A cycle in a directed graph is a path that follows edge directions and leads back to the starting vertex. More precisely, there exist vertices v0, v1, ..., vk where v0 = vk and there is a directed edge from each vi to vi+1.
The key word here is "directed." In an undirected graph, if A connects to B and B connects to A, that is just one edge, not a cycle. But in a directed graph, edges have direction. A pointing to B does not mean B points to A. A cycle only exists when you can follow the arrows and return to where you started.
Consider this directed graph:
Vertices B, C, and D form a cycle: B -> C -> D -> B. You can start at B, follow the arrows through C and D, and end up back at B. Notice that A is not part of the cycle, even though A has an edge to B. Following the arrows from A, you can reach the cycle, but A itself is not in the loop.
A directed graph without any cycles is called a DAG (Directed Acyclic Graph). DAGs are incredibly useful because they can be topologically sorted, meaning you can line up all the vertices so that every edge points forward. If a cycle exists, topological sorting is impossible, because there is no way to order vertices in a circle so that every edge goes "forward."
Why Parent Tracking Fails for Directed Graphs
If you have studied cycle detection in undirected graphs, you know the standard approach: run DFS, and if you visit a neighbor that has already been visited and is not the parent of the current node, you have found a cycle. This works perfectly for undirected graphs. But it completely breaks down for directed graphs.
Here is why. Consider this directed graph:
This graph has no cycle. A points to B and C, and B also points to C. There is no way to follow the arrows and return to any starting vertex.
But if you run the undirected cycle detection algorithm, here is what happens. Start DFS from A, visit B (mark as visited), then from B visit C (mark as visited). Backtrack to A, now try to visit C from A. C is already visited and is not the "parent" of A, so the algorithm incorrectly reports a cycle.
The problem is that in a directed graph, reaching a previously visited node does not mean there is a cycle. It could just mean two different paths converge at the same node. Vertex C is reachable from A via two paths (A -> C directly, and A -> B -> C), but that is not a cycle.
What you actually need to detect is whether you reach a node that is currently on your DFS call stack, meaning a node that you started processing but have not finished processing. That is the difference between a node you have seen before (which is harmless in a directed graph) and a node that is part of your current exploration path (which means you have found a way back to it, forming a cycle).
This is exactly what the three-coloring technique solves.
Approach 1: DFS with Three-Coloring (White/Gray/Black)
The three-coloring technique assigns one of three states to every vertex during DFS:
- WHITE (0): The vertex has not been visited yet. It has not been touched by DFS at all.
- GRAY (1): The vertex is currently being processed. DFS has entered this vertex but has not finished exploring all of its descendants. It is on the current recursion stack.
- BLACK (2): The vertex is fully processed. DFS has explored all of its descendants and backtracked past it.
The key insight is simple: if during DFS you encounter a GRAY vertex, you have found a cycle. A GRAY vertex is one that is currently on your DFS path, meaning you started from it (or an ancestor of it) and have now found a way back to it by following directed edges. That is exactly what a cycle is.
If you encounter a BLACK vertex, there is no cycle through that vertex, because all of its descendants have already been fully explored and none of them led back to it.
If you encounter a WHITE vertex, you have not explored it yet, so you continue the DFS into it.
How the Algorithm Works
- Initialize all vertices as WHITE.
- For each WHITE vertex, start a DFS.
- When you enter a vertex, color it GRAY.
- Explore all of its neighbors:
- If a neighbor is WHITE, recurse into it.
- If a neighbor is GRAY, you have found a cycle. Return true.
- If a neighbor is BLACK, skip it (already fully explored, no cycle through it).
- When you finish processing all neighbors and backtrack, color the vertex BLACK.
- If no GRAY neighbor is ever encountered, the graph has no cycle.
Visualizing the Coloring Process
Let us trace through a graph with a cycle. Consider the graph A -> B -> C -> D -> B (with an extra edge A -> E):
Step 1: Start DFS at A. Color A as GRAY.
Step 2: Visit B (neighbor of A). Color B as GRAY.
Step 3: Visit C (neighbor of B). Color C as GRAY.
Step 4: Visit D (neighbor of C). Color D as GRAY.
Step 5: From D, look at neighbor B. B is GRAY. We have found a cycle: B -> C -> D -> B.
The algorithm stops and reports that a cycle exists.
Implementation
Complexity
- Time: O(V + E), where V is the number of vertices and E is the number of edges. Every vertex is visited once (transitions from WHITE to GRAY to BLACK), and every edge is examined once.
- Space: O(V) for the color array plus O(V) for the recursion stack in the worst case, giving O(V) total.
Approach 2: Kahn's Algorithm (Topological Sort)
The second approach takes a completely different angle. Instead of DFS, it uses BFS and the concept of in-degrees.
The idea comes from a simple observation: in a DAG (a directed graph with no cycles), there must be at least one vertex with in-degree 0, meaning no edges point to it. Think of it as a starting point, something with no prerequisites. If every vertex has at least one incoming edge, then you can follow incoming edges in a loop forever, which means a cycle exists.
Kahn's algorithm builds on this observation. It repeatedly removes vertices with in-degree 0 and their outgoing edges, peeling the graph layer by layer. If the graph is a DAG, eventually all vertices will be removed. If a cycle exists, the vertices in the cycle will never reach in-degree 0 (because they depend on each other), so they will never be removed.
How the Algorithm Works
- Compute the in-degree of every vertex.
- Add all vertices with in-degree 0 to a queue.
- While the queue is not empty:
- Remove a vertex from the queue.
- Increment a processed counter.
- For each neighbor, decrement its in-degree by 1. If the in-degree becomes 0, add it to the queue.
- After the loop, if the processed count equals the total number of vertices, the graph is a DAG (no cycle). If it is less, the remaining vertices form one or more cycles.
Visualizing Kahn's Algorithm
Consider this graph with 6 vertices:
In-degrees: A=0, B=1, C=2, D=2, E=1
Step 1: A has in-degree 0. Add A to queue. Process A. Decrement in-degrees of B and C. Now B=0, C=1.
Step 2: B has in-degree 0. Process B. Decrement in-degree of D. Now D=1.
Step 3: Queue is empty. No more vertices with in-degree 0. But we only processed 2 out of 6 vertices. The remaining vertices (C, D, E) form a cycle: C -> D -> E -> C.
So the algorithm correctly reports a cycle.
Implementation
Complexity
- Time: O(V + E). Computing in-degrees takes O(V + E). The BFS loop processes each vertex and edge at most once.
- Space: O(V) for the in-degree array and the queue.
Comparison of Approaches
| Criteria | DFS Three-Coloring | Kahn's Algorithm (BFS) |
|---|---|---|
| Time Complexity | O(V + E) | O(V + E) |
| Space Complexity | O(V) | O(V) |
| Traversal Type | DFS (recursive/stack) | BFS (queue) |
| Detects Cycle | Yes | Yes |
| Gives Topological Order | With modification (reverse post-order) | Yes, naturally |
| Can Find Cycle Vertices | Easier (track the GRAY path) | Harder (remaining unprocessed vertices) |
| Stack Overflow Risk | Yes, for very deep graphs | No (iterative) |
| Implementation Complexity | Simpler for basic detection | Slightly more setup (in-degree computation) |
| Best For | Quick cycle detection, finding the actual cycle path | Topological sort + cycle detection together |
When should you pick one over the other?
- Use DFS Three-Coloring when you need to detect a cycle and possibly find the exact vertices in the cycle. It is also the more natural choice when you are already doing DFS for other purposes (like finding connected components or paths).
- Use Kahn's Algorithm when you need both cycle detection and a topological ordering, or when the graph is very deep and you want to avoid recursion stack overflow. Since it is iterative, it handles large graphs without stack issues.
Step-by-Step Walkthrough
Let us trace through both algorithms on a more complex graph to solidify your understanding. Consider the following directed graph with 7 vertices:
The cycle here is 3 -> 4 -> 5 -> 3.
DFS Three-Coloring Trace
Assume adjacency list ordering processes neighbors in ascending order.
| Step | Action | Colors (0-6) | Stack |
|---|---|---|---|
| 1 | Start DFS at 0 | GRAY W W W W W W | [0] |
| 2 | Visit 1 (neighbor of 0) | GRAY GRAY W W W W W | [0, 1] |
| 3 | Visit 3 (neighbor of 1) | GRAY GRAY W GRAY W W W | [0, 1, 3] |
| 4 | Visit 4 (neighbor of 3) | GRAY GRAY W GRAY GRAY W W | [0, 1, 3, 4] |
| 5 | Visit 5 (neighbor of 4) | GRAY GRAY W GRAY GRAY GRAY W | [0, 1, 3, 4, 5] |
| 6 | Check neighbor 3 of 5 | 3 is GRAY. Cycle found! | [0, 1, 3, 4, 5] |
The algorithm detects the cycle at step 6 when vertex 5 tries to visit vertex 3, which is GRAY (on the current path). The cycle is 3 -> 4 -> 5 -> 3.
Kahn's Algorithm Trace
In-degrees: 0=0, 1=1, 2=1, 3=3, 4=1, 5=1, 6=1
| Step | Queue | Process | Update In-degrees | Processed |
|---|---|---|---|---|
| Init | [0] | - | - | 0 |
| 1 | [] | 0 | 1: 1->0, 2: 1->0 | 1 |
| 2 | [1, 2] | 1 | 3: 3->2 | 2 |
| 3 | [2] | 2 | 3: 2->1 | 3 |
| 4 | [] | - | Queue empty | 3 |
After processing, only 3 out of 7 vertices were processed. The remaining vertices (3, 4, 5, 6) could not be processed because their in-degrees never reached 0. Vertices 3, 4, and 5 form the cycle, and vertex 6 depends on vertex 4 which is stuck in the cycle. The algorithm correctly reports a cycle because 3 is not equal to 7.