Cycle Detection in a Directed Graph
Grey, still on the path
- A
Black, finished
Nothing yet.
- Not reached
- Waiting
- Current
- Finished
1/20
Colour A grey: it is on the path we are exploring.
Settings
Graph
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 | Whether there is a cycle, 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. On the graph with a cycle, topological sort gets stuck, because a cycle leaves no valid order.