How Cycle Detection Works
Cycle detection in a directed graph is a depth-first search that colours vertices white, grey and black. Reaching a grey vertex means you have walked back onto your own path — a cycle.
- A
Nothing yet.
- Not reached
- Waiting
- Current
- Finished
Step 1 of 20
Colour A grey: it is on the path we are exploring.
Counters
- Visited
- 1/8
- On the path
- 1
- Cycle
- none yet
- Nodes on it
- -
Settings
Cycle detection
- 1
colour[v] = white for all v - 2
- 3
visit(v): - 4
colour[v] = grey - 5
for each neighbour w: - 6
if colour[w] == grey: - 7
CYCLE - w is still on the path - 8
if colour[w] == white: visit(w) - 9
colour[v] = black
What each one answers
| Algorithm | What it answers | Time | Needs |
|---|---|---|---|
| Breadth-first | Fewest hops from the start | O(V + E) | A queue |
| Depth-first | Reachability, one branch at a time | O(V + E) | A stack |
| Cycle detection | Does a cycle exist, and where | O(V + E) | Node colours |
| Topological sort | A valid order to do the work in | O(V + E) | No cycles |
| Dijkstra | Cheapest path by edge weight | O(E log V) | Non-negative weights |
V is the number of nodes and E the number of edges. Switch to the graph with a cycle and the topological sort gets stuck: once a cycle exists there is no valid order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(V + E) | O(V + E) | O(V + E) | O(V) |
One DFS. The colours are what make it work: a plain visited set cannot tell 'already finished' from 'currently on the stack', and only the second one is a cycle.
How cycle detection works
Colour every vertex white to begin with. A depth-first search turns a vertex grey when it enters and black when it finishes, so grey means exactly "on the path I am currently walking". An edge into a black vertex is harmless — that part of the graph is done. An edge into a grey vertex is a back edge: it points at a vertex still on the stack, which means there is a path from it to here and an edge from here to it. That is a cycle.
- Colour all vertices white.
- Start a DFS from any white vertex, colouring it grey on entry.
- Follow each edge: a white neighbour is recursed into, a grey neighbour means a cycle has been found.
- Colour the vertex black when all its edges are exhausted, and return.
- Repeat from any remaining white vertex, since the graph may be disconnected.
Implementation
The same algorithm the visualiser is running, written to be read.
WHITE, GREY, BLACK = 0, 1, 2
def has_cycle(graph):
colour = {node: WHITE for node in graph}
def visit(node):
colour[node] = GREY
for neighbour in graph[node]:
# Grey means "still on the current path" - that is a back edge.
if colour[neighbour] == GREY:
return True
if colour[neighbour] == WHITE and visit(neighbour):
return True
colour[node] = BLACK
return False
return any(colour[node] == WHITE and visit(node) for node in graph)When to use it
- Use it before a topological sort — a cyclic dependency graph has no valid order, and this is how you produce a useful error instead of a wrong answer.
- Use it to catch circular imports, circular foreign keys, deadlock cycles in a wait-for graph, and infinite loops in a state machine.
- Note that undirected graphs are a different problem: there, any edge back to a visited vertex that is not the one you came from is a cycle, so a parent check replaces the colours.
Check yourself
If the animation made sense, these should too.
Why is a plain visited set not enough to detect a cycle in a directed graph?
Because it cannot distinguish 'already finished' from 'currently on the path I am walking'. Only the second is a cycle. The three colours make the difference explicit: an edge to a grey vertex is a back edge, an edge to a black one is harmless.
How does cycle detection differ on an undirected graph?
There, any edge to an already visited vertex closes a cycle - except the edge you arrived by. So the colours are replaced by a parent check, and forgetting that check reports every single edge as a cycle.