Recursion Stack
We keep track of nodes currently in the DFS path. If we visit a node already in the stack, a cycle exists.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
Cycles in directed graphs are detected by finding back-edges during DFS. A back-edge points from a node to an ancestor currently in the recursion stack.
We keep track of nodes currently in the DFS path. If we visit a node already in the stack, a cycle exists.
A back-edge is an edge from a node to one of its ancestors in the DFS tree. This is the definitive indicator of a directed cycle.
Every node and edge is explored once. If the DFS completes without finding any back-edges, the graph is a Directed Acyclic Graph (DAG).
Nodes can be in three states: unvisited, currently visiting (in stack), or fully visited (processed).