Algorithms / Graph Cycle Detection
Least You Need to Know: Cycle Detection in Directed and Undirected Graphs
Cycle detection depends on graph type. In undirected graphs, you must ignore the edge back to the parent. In directed graphs, the key signal is whether DFS re-enters a node that is still on the current recursion path.
The least you need to know
- In undirected DFS, seeing the parent again is normal and not a cycle.
- In directed DFS, a back edge to the active recursion stack signals a cycle.
- Union-find can detect whether adding an undirected edge closes a cycle.
- Kahn's algorithm detects directed cycles when not all nodes can be removed.
- Tree-specific edge-count shortcuts work only under additional connectivity assumptions.
Key notation
parent
the previous node in undirected DFS
recursion stack
nodes currently active on the DFS path
back edge
edge to an ancestor on the current DFS path
Tiny worked example
- In a directed graph, DFS marks nodes as unvisited, active, or finished.
- When DFS follows an edge to an active node, it has found a cycle on the current path.
- In an undirected graph, that same check must ignore the edge back to the parent.
Common mistakes
- Students often reuse undirected cycle logic on directed graphs.
- Students often call every visited neighbor a cycle in undirected DFS, incorrectly counting the parent edge.
- Students often forget that union-find is naturally for edge additions in undirected connectivity settings.
How to recognize this kind of problem
- The prompt asks whether prerequisites are impossible because of a dependency loop.
- The graph type matters: directed and undirected need different reasoning.
- You only need to know whether some cycle exists, not necessarily all simple cycles.