What is the approach to detect a cycle in a directed graph?
Candidates must explain algorithms like DFS with coloring or Kahn's algorithm to identify cycles in a directed graph structure.
Why Interviewers Ask This
Cycle detection is critical for dependency resolution, deadlock prevention, and topological sorting scenarios. Interviewers assess your ability to manage visited states and distinguish between active and completed nodes. It tests logical reasoning about graph properties and the correctness of traversal algorithms. Understanding this concept is essential for systems that rely on DAG structures.
How to Answer This Question
Explain the DFS-based approach using three colors: white (unvisited), gray (visiting), and black (visited). Describe how encountering a gray node indicates a back edge and thus a cycle. Alternatively, discuss Kahn's algorithm using in-degree counts. Provide a small example graph to trace the logic. Emphasize why undirected graphs require different handling than directed ones.
Key Points to Cover
- Three-color DFS state machine
- Back edge identification
- Difference between directed and undirected cycle detection
- Linear time complexity O(V+E)
Sample Answer
I would use Depth First Search with a state tracking system. Nodes start unvisited. When visiting a node, mark it as currently visiting. If we encounter a neighbor that is already currently visiting, a cycle exists. Once…
Common Mistakes to Avoid
- Confusing back edges with cross edges in undirected graphs
- Not resetting visited states correctly between disconnected components
- Using BFS incorrectly for cycle detection in directed graphs
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.