Cycle Detection in Directed Graph (DFS)
HardA back edge into the current recursion path
Problem
Detect a cycle in a directed graph using DFS with a recursion stack.
DFS with three colours; seeing a node still 'in progress' (grey) means you've found a back-edge cycle.
The idea
In a directed graph, seeing a visited vertex is not enough — it may simply have been finished earlier. Keep a second flag for vertices on the current recursion stack; reaching one of those is a genuine cycle.
The trick
- Two marks: visited ever, and on the current path.
- Clear the on-path flag as the recursion returns.
- Kahn's algorithm detects the same thing by counting how many vertices it can order.
Step 1 of 6. Kahn's algorithm: repeatedly take a course with 0 remaining prerequisites. indegrees [0,1,2,1].
Cycle ⇒ impossible.
1q = every course whose indegree is 02while q not empty:3 c = q.pop(); processed += 14 for nb in adj[c]: indeg[nb] -= 1; if now 0, q.push(nb)5return processed == numCoursesInput
- nodes
- 4, 4 edges
Memory
- indegrees
- [0,1,2,1]
- processed
- —
Output
- finish
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n=4, edges=[[0,1],[1,2],[2,3],[3,1]]
- Output:
- true
- Explanation:
- 3→1 closes a directed loop.
Example 2
- Input:
- n=3, edges=[[0,1],[1,2]]
- Output:
- false
- Explanation:
- A straight chain → no cycle.
Example 3
- Input:
- n=2, edges=[[0,1],[1,0]]
- Output:
- true
- Explanation:
- Mutual arrows form a cycle.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.