How do you detect a cycle in a Directed Graph?

Difficulty: 5/10

DFS, Kahn's algorithm, graph traversal

Directed Graph Cycle Detection

For a directed graph, DFS cycle detection uses two states: visited and currently-in-recursion-stack. If DFS encounters an edge to a vertex that is already in the current recursion stack, it has found a back edge and therefore a cycle.

javascript

1
visited tracks globally discovered vertices.
2
inStack tracks the current DFS path.
3
An edge to an in-stack vertex indicates a directed cycle.
4
Time complexity: O(V+E).
5
Kahn's topological-sort approach can also detect directed cycles.

Scenario Questions

0-2 years experience

Follow-up Questions