DFS Cycle Detection (Directed Graph)
What common mistakes do candidates make around DFS Cycle Detection (Directed Graph), and how do you avoid them?
Answers use simple, clear English.
Quick interview answer
Common mistakes: Using two-color visited only (misses cross edges in undirected); forgetting disconnected components. Best practices: Loop all nodes as DFS roots; explain gray = active recursion path.
Detailed answer
Common mistakes: Using two-color visited only (misses cross edges in undirected); forgetting disconnected components. Best practices: Loop all nodes as DFS roots; explain gray = active recursion path. Core: Three-color DFS: white=unvisited, gray=in current stack, black=done. Back edge to gray node ⇒ cycle. Works for dependency graphs and course prerequisites. Real-time example: Build pipeline: detect circular module imports before CI runs. Pros: O(V+E); distinguishes directed vs undirected cycle logic. Cons: Recursive DFS risks stack overflow on huge graphs; use iterative + explicit stack. Common mistakes: Using two-color visited only (misses cross edges in undirected); forgetting disconnected components. Best practices: Loop all nodes as DFS roots; explain gray = active recursion path. Audience level: Fresher.
Full explanation
Three-color DFS: white=unvisited, gray=in current stack, black=done. Back edge to gray node ⇒ cycle. Works for dependency graphs and course prerequisites.
Real example & use case
Build pipeline: detect circular module imports before CI runs.
Pros & cons
Pros: O(V+E); distinguishes directed vs undirected cycle logic. Cons: Recursive DFS risks stack overflow on huge graphs; use iterative + explicit stack.
Common mistakes
Using two-color visited only (misses cross edges in undirected); forgetting disconnected components.
Best practices
Loop all nodes as DFS roots; explain gray = active recursion path.
Follow-up questions
Open one as its own read / solve / listen card