DFS Cycle Detection (Directed Graph)
Give a real production-style example of using DFS Cycle Detection (Directed Graph). Walk through the scenario end-to-end.
Answers use simple, clear English.
Quick interview answer
Scenario: Build pipeline: detect circular module imports before CI runs. Implementation notes: Loop all nodes as DFS roots; explain gray = active recursion path.
Detailed answer
Scenario: Build pipeline: detect circular module imports before CI runs. Implementation notes: 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: Tech Lead.
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