How Do You Detect a Cycle in a Directed Graph?
Learn the three-state DFS technique to detect cycles in a directed graph, with complexity analysis and Python code.
Expected Interview Answer
You detect a cycle in a directed graph with DFS that tracks each node's state as unvisited, in the current recursion path, or fully processed — a cycle exists if the traversal ever reaches a node that is still in the current path, called a back edge.
Every node starts unvisited; when DFS enters a node it marks it as being in the current recursion path, and when DFS finishes exploring all of that node's descendants it marks it fully processed and removes it from the path. If a neighbor is currently in the recursion path, that edge points backward into an ancestor, forming a cycle. Simply tracking a global visited set is not enough, because a node reachable through two separate branches looks like a repeat visit even without a cycle; the three-state coloring (white, gray, black) is what correctly distinguishes a cross edge from a true back edge. This runs in O(V + E) time and is exactly the check used to detect deadlock cycles and invalid dependency graphs before running Kahn's topological sort.
- O(V + E) time with a single DFS pass
- Correctly distinguishes back edges from cross/forward edges
- Directly enables build systems and schedulers to reject circular dependencies
- Prerequisite check before running topological sort
AI Mentor Explanation
A selector tracing a chain of “must bat before” substitution rules walks down the batting order, marking each player as “currently being resolved” while following their required substitute. If that chain of substitutions ever loops back to a player already marked “currently being resolved” in this same chain, the substitution rules are circular and nobody can actually bat first. A player who was fully resolved earlier and is revisited through a totally different chain is not a problem — only revisiting someone still open in the current chain signals a cycle. This state-tracking, not just a simple already-seen check, is what correctly finds cycles in a directed dependency graph.
Step-by-Step Explanation
Step 1
Track three states per node
Unvisited (white), in the current recursion path (gray), fully processed (black).
Step 2
Mark gray on entry
When DFS visits a node, mark it gray before recursing into its neighbors.
Step 3
Check neighbor states
A gray neighbor means a back edge and a cycle; a black neighbor is safe to skip.
Step 4
Mark black on exit
After all neighbors are explored, mark the node black to remove it from the active path.
What Interviewer Expects
- Explain why a simple visited set is insufficient for directed graphs
- Describe the three-state (white/gray/black) coloring clearly
- State the O(V + E) time complexity
- Connect cycle detection to prerequisite checks before topological sort
Common Mistakes
- Using only a single visited set, which cannot distinguish cross edges from back edges
- Forgetting to unmark a node from the recursion path after finishing its DFS branch
- Assuming the technique for undirected graphs (parent tracking) applies directly to directed graphs
- Not handling multiple disconnected components in the graph
Best Answer (HR Friendly)
“To detect a cycle in a directed graph, I do a depth-first search and keep track of which nodes are still being explored in the current path versus fully finished. If I ever follow an edge into a node that is still open in my current path, that means I have looped back on myself, which is a cycle.”
Code Example
WHITE, GRAY, BLACK = 0, 1, 2
def has_cycle(graph):
state = {node: WHITE for node in graph}
def dfs(node):
state[node] = GRAY
for neighbor in graph[node]:
if state[neighbor] == GRAY:
return True
if state[neighbor] == WHITE and dfs(neighbor):
return True
state[node] = BLACK
return False
return any(state[n] == WHITE and dfs(n) for n in graph)Follow-up Questions
- How would you print the actual cycle once one is detected?
- How does this three-state approach differ from cycle detection in an undirected graph?
- How would you detect a cycle without recursion, using an explicit stack?
- How does this check relate to Kahn's algorithm for topological sorting?
MCQ Practice
1. Which edge type indicates a cycle in directed-graph DFS cycle detection?
A back edge points to a node still in the current recursion path (gray), which forms a cycle.
2. Why is a single visited/unvisited flag insufficient for directed cycle detection?
Without a third "in current path" state, revisiting an already-finished node looks identical to hitting a real cycle.
3. What is the time complexity of directed cycle detection using DFS?
Each vertex and edge is processed once during the DFS traversal, giving O(V + E).
Flash Cards
What three states does directed cycle detection track per node? — White (unvisited), gray (in current path), black (fully processed).
What signals a cycle during the DFS? — Encountering a neighbor that is currently gray (a back edge).
Why not just use a simple visited set? — It cannot tell a harmless cross edge apart from a true back edge forming a cycle.
What is a real-world use of directed cycle detection? — Detecting circular dependencies in build systems or task schedulers.