DFS Cycle Detection (Directed Graph)
You are a Junior on-call. A production issue might involve DFS Cycle Detection (Directed Graph). How do you diagnose and mitigate?
Answers use simple, clear English.
Audio N/AQuick interview answer
Mitigate first, then root-cause. Check symptoms against: Using two-color visited only (misses cross edges in undirected); forgetting disconnected components..
Detailed answer
Mitigate first, then root-cause. Check symptoms against: Using two-color visited only (misses cross edges in undirected); forgetting disconnected components.. Validate with: Loop all nodes as DFS roots; explain gray = active recursion path.. Context: Three-color DFS: white=unvisited, gray=in current stack, black=done. Back edge to gray node ⇒ cycle. Works for dependency graphs and course prerequisites. 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: Junior.
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