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, which is a cycle.
- A
Nothing yet.
- Not reached
- Waiting
- Current
- Finished
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
More options
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 |
Scroll the table sideways for the rest of the columns.
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
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)