Module 23
Cycle Detection
Find loops in graphs: parent tracking and union-find for undirected graphs, three-colour DFS for directed graphs, and functional graphs.
A cycle is a path that comes back to where it started. Detecting one answers practical questions: can these courses be finished (no circular prerequisites), is this network a tree, which connection is redundant, will this process loop forever?
Undirected and directed graphs need different checks. In an undirected graph, meeting any already-visited node other than your parent means a cycle. In a directed graph, that isn't enough: you must know whether the node is still on the current DFS path, which is what the three-colour method tracks.
Best after: Depth-First Search
Part 1
Learn the ideas
- 23.1Cycles in Undirected GraphsDuring DFS or BFS, an edge to a visited node that isn't your parent closes a cycle. Union-find spots it as an edge whose endpoints are already in the same group.12 min
- 23.2Cycles in Directed Graphs: Three ColoursWhite = unvisited, grey = on the current DFS path, black = finished. An edge to a grey node is a back edge, and that means a cycle.14 min
- 23.3One Outgoing Edge: Functional GraphsWhen every node points to at most one next node, each walk is a path that ends or falls into exactly one cycle. Timestamps find cycle lengths in O(n).8 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Tree = n − 1 edges and no cycle (which together imply connected).
The first edge that joins two already-connected nodes is the one that closed the cycle.
Can all tasks finish? Only if the dependency graph has no directed cycle.
Colours as results: a node is safe when every path from it ends, i.e. it can't reach a cycle.
Undirected cycle detection on an implicit grid graph, remembering the parent cell.
Functional graphs: walk with timestamps to measure each cycle once.