Lesson 23.2 · Cycle Detection
Cycles in Directed Graphs: Three Colours
White = 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
Think of it like this
Following a chain of "see also" references in a manual. If a reference points to a page you're still reading further up your chain, you're in a loop. If it points to a page you've already fully read and closed, that's fine, it's just a shared page.
1.Why "visited" isn't enough
In a directed graph, two different paths can reach the same node without any cycle (0 → 1 → 2 and 0 → 2). A simple visited flag would wrongly report a cycle when 0 → 2 finds 2 already visited. The question is whether 2 is still on the current path.
So keep three states: 0 = white (not seen), 1 = grey (entered, not finished), 2 = black (finished). Set grey on entry and black on exit. An edge to a grey node goes back up the current path: a cycle. An edge to a black node is harmless.
edges = [[0,1],[1,2],[0,2]]Step 1/7Enter 0: grey (amber).
2.Kahn's algorithm says the same thing
Topological sort by repeatedly removing nodes with in-degree 0 (Module 24) processes every node exactly when the graph has no cycle. If some nodes are never removed, they're on or behind a cycle. It's an iterative alternative to the three colours.
Remember
- Grey = on the current path.
- Edge to grey = back edge = cycle.
- Black nodes can be safely reached again.
Common mistakes
- Marking black before exploring the children.
- Resetting colours between DFS starts (wasted work).
Words used in this lesson
- Back edge
- An edge from a node to one of its ancestors on the current DFS path.
- Functional graph
- A directed graph where each node has at most one outgoing edge.