ORIGINAL TECHNICAL PRACTICE
Detect a directed dependency cycle
How would you determine whether a build dependency graph contains a directed cycle and return a useful explanation?
Written for independent practice. The model answer presents one approach; clarify constraints and explain alternatives.
A REASONED APPROACH
Model answer.
A depth-first search can track unvisited, active and completed nodes. An edge to an active node indicates a cycle; parent links can reconstruct a concrete cycle rather than reporting only a boolean.
Work through it
- Normalize the graph so vertices with no outgoing edges still exist, and include all disconnected components in the search.
- Mark a node active on entry and completed on exit. An edge to a completed node is not evidence of a cycle.
- For an active neighbor, trace parent links back to that neighbor and return the resulting cycle path. A self-loop should also be reported.
Tradeoffs to discuss
- Traversal costs O(V+E) time and O(V) state. Kahn’s indegree algorithm also detects a cycle, but a leftover-node set is not itself a reconstructed cycle.
Common pitfalls
- A single visited flag cannot distinguish an active ancestor from a completed branch. Recursive traversal may exceed the language’s call-stack limit on deep graphs.