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.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
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
مختصر حل شدہ مثال
- 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.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Modeling Interview Problems as Graph Search.
Least You Need to Know: Modeling Interview Problems as Graph SearchRelated lessons
Keep going with nearby lessons in the same topic.