Sign in to watch this lesson
Algorithms - Graphs I · 4:45
Finding a Cycle
A deadlock is a cycle in the wait-for graph, and a depth-first search with three colours finds one: in a directed graph, an edge into a gray vertex (one still on the current path) closes a cycle, while an edge into a black, finished vertex never does. Parent pointers then rebuild the cycle itself, 1 2 3 1 on our example. Undirected graphs need only a visited flag plus skipping the edge you arrived on (by edge id, for parallel edges), and functional graphs split into one cycle with trees flowing in.
You will learn
- Detect a cycle in a directed graph in O(n + m) with white/gray/black colouring, and explain why only an edge into a gray vertex closes a cycle
- Recover and print the cycle from cycle_start, cycle_end and parent pointers
- Detect cycles in undirected graphs with a visited flag, skipping the arrival edge by id so parallel edges count
- Decompose a functional graph (out-degree 1) into cycles with in-trees, iteratively, and know when Floyd's two pointers are the better tool