~/graphs/cycle-detection
Cycle detection
Find out whether a directed graph loops back on itself: DFS with three colours spots the edge that closes a cycle.
DFS that colours nodes white (unseen), gray (on the current path) and black (finished). An edge into a gray node closes a cycle.
Dependencies, prerequisites, deadlocks, redirects or pointers that might loop, and you need to know if they do, or where.
O(V + E)
O(V + E)
You’ll recognise it when
- Things point at other things and might loop: prerequisites, imports, build targets, symlinks, redirects, “waits for” locks.
- The question is “is this possible at all?”: can every course be finished, can the build run, is there a deadlock?
- You’re asked to print a loop if one exists, or to find the nodes that can never reach one (“safe” states).
- A linked list or a function
x → f(x)might come back to where it’s been.
It sits right next to topological sort: a directed graph has a topological order exactly when it has no cycle, and Kahn’s algorithm answers the same yes/no question. Use the DFS below when you also want the cycle itself.
The idea
Think of walking through a building and unrolling a ball of string behind you, as in the Minotaur’s maze. When you reach a dead end, you wind the string back up to the last junction. If you ever walk into a room and find your own string already there, you’ve gone in a circle. Finding a room you visited earlier, after you wound the string back out of it, means nothing: you just reached it by a second route.
That’s the whole trick. DFS keeps the current path from the start to where it is now, the string. Each node has a state:
- white: not seen yet;
- gray: on the current
path(the string runs through it); - black: finished: every edge out of it has been followed, and it’s off the path again.
An edge to a gray node points back up the string: the path already leads from that node down to here, so the edge closes a loop. An edge to a black node is harmless. Everything past a black node was explored while it was gray, and none of it led onto the path, or the search would have stopped there.
How it works
The input is n nodes numbered from 0 and a list of directed edges. The graphic follows the steps as you scroll. Gray nodes are drawn in the “active” colour and black ones in the “done” colour; the legend at the top of the graphic spells this out.
- Start: every node is white.
- Pick the first white node, colour it gray, and make it the whole
path. Here that’s node 0. - Look at the top of the
path,node, and follow its next untried edge tonxt. - If
nxtis white, step into it: it turns gray and is pushed on thepath. - When
nodehas no untried edges left, it turns black and is popped off thepath. Node 3 has no edges at all, so it’s done right away. - An edge into a black node is not a cycle: 2 → 3 reaches 3 a second time, but 3 is finished and off the path. Skip it.
- When the
pathempties, the outer loop starts a fresh search from the next white node, here 4. Several searches cover a graph that isn’t all reachable from node 0. - An edge into a gray node closes a cycle: 6 → 4 leads back to 4, which is still on the
path. The cycle is thepathfrom 4 to the end, 4 → 5 → 6, plus this edge.
Why it’s correct: the gray nodes are always exactly the current path, one chain of edges from the search’s start. So an edge into a gray node always closes a loop. The other way round, if a cycle exists, take the first of its nodes the search reaches. While that node is gray, the search walks everything reachable from it, including the rest of the cycle, and the cycle’s last edge then leads straight back to it while it’s still gray.
With the edge 6 → 4 removed, the same search finds no cycle: every node ends black.
The code keeps the stack by hand: path holds the gray nodes and tried remembers how far each one got through its edges. A recursive DFS is shorter, but a long chain would hit Python’s recursion limit of 1,000.
WHITE, GRAY, BLACK = 0, 1, 2 # not seen, on the current path, finished
def find_cycle(n, edges):
"""Return the nodes of one directed cycle, in order, or None if there is none."""
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
state = [WHITE] * n
for start in range(n):
if state[start] != WHITE:
continue
state[start] = GRAY
path = [start] # the gray nodes, in the order we entered them
tried = [0] # tried[i]: how many edges of path[i] we've followed
while path:
node = path[-1]
if tried[-1] == len(adj[node]):
state[node] = BLACK
path.pop()
tried.pop()
continue
nxt = adj[node][tried[-1]]
tried[-1] += 1
if state[nxt] == GRAY: # an edge back onto the path
return path[path.index(nxt):]
if state[nxt] == BLACK: # finished: no way back from it
continue
state[nxt] = GRAY
path.append(nxt)
tried.append(0)
return None#include <algorithm>
#include <utility>
#include <vector>
enum State { WHITE, GRAY, BLACK }; // not seen, on the current path, finished
// Returns the nodes of one directed cycle, in order, or an empty vector if there is none.
std::vector<int> findCycle(int n, const std::vector<std::pair<int, int>>& edges) {
std::vector<std::vector<int>> adj(n);
for (auto [u, v] : edges) adj[u].push_back(v);
std::vector<State> state(n, WHITE);
for (int start = 0; start < n; start++) {
if (state[start] != WHITE) continue;
state[start] = GRAY;
std::vector<int> path = {start}; // the gray nodes, in the order we entered them
std::vector<size_t> tried = {0}; // tried[i]: how many edges of path[i] we've followed
while (!path.empty()) {
int node = path.back();
if (tried.back() == adj[node].size()) {
state[node] = BLACK;
path.pop_back();
tried.pop_back();
continue;
}
int nxt = adj[node][tried.back()];
tried.back()++;
if (state[nxt] == GRAY) { // an edge back onto the path
auto from = std::find(path.begin(), path.end(), nxt);
return std::vector<int>(from, path.end());
}
if (state[nxt] == BLACK) { // finished: no way back from it
continue;
}
state[nxt] = GRAY;
path.push_back(nxt);
tried.push_back(0);
}
}
return {};
}import java.util.*;
class CycleFinder {
static final int WHITE = 0, GRAY = 1, BLACK = 2; // not seen, on the current path, finished
// Returns the nodes of one directed cycle, in order, or null if there is none.
static List<Integer> findCycle(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(e[1]);
int[] state = new int[n];
for (int start = 0; start < n; start++) {
if (state[start] != WHITE) continue;
state[start] = GRAY;
List<Integer> path = new ArrayList<>(List.of(start)); // the gray nodes, in order
List<Integer> tried = new ArrayList<>(List.of(0)); // edges of path[i] followed
while (!path.isEmpty()) {
int top = path.size() - 1;
int node = path.get(top);
if (tried.get(top) == adj.get(node).size()) {
state[node] = BLACK;
path.remove(top);
tried.remove(top);
continue;
}
int nxt = adj.get(node).get(tried.get(top));
tried.set(top, tried.get(top) + 1);
if (state[nxt] == GRAY) { // an edge back onto the path
return new ArrayList<>(path.subList(path.indexOf(nxt), path.size()));
}
if (state[nxt] == BLACK) { // finished: no way back from it
continue;
}
state[nxt] = GRAY;
path.add(nxt);
tried.add(0);
}
}
return null;
}
}Why it’s O(V + E)
Each node turns gray once and black once, so the outer loop and all the pushes and pops cost O(V). Each edge is followed exactly once, when its start node is at the top of the path: O(E). Slicing out the cycle at the end is O(V) and happens once.
Space is the adjacency lists, O(V + E), plus state, path and tried, each O(V).
Common mistakes
Using one visited set
With only “seen” and “not seen”, any node reached twice looks like a cycle. The diamond 0 → 1 → 3, 0 → 2 → 3 has no cycle, but 3 is reached twice. You need the difference between on the path (gray) and finished (black).
if nxt in visited: return True # ✗ 3 is visited, but not a cycle
if state[nxt] == GRAY: return True # ✓ only the current path countsNever turning nodes black
If a node stays gray after its search is done, a later branch that reaches it reports a cycle that isn’t there. Mark it black when its last edge has been tried, before popping it.
path.pop() # ✗ it's still gray
state[node] = BLACK; path.pop() # ✓ off the path, and marked soReturning the whole path as the cycle
The path can have a tail before the loop starts. In the example it was 4 → 5 → 6, but if the search had begun at a node that points into 4, that node would be on the path too. The cycle starts where nxt sits on the path.
return path # ✗ includes the tail
return path[path.index(nxt):] # ✓ just the loopUsing the directed test on an undirected graph
In an undirected graph, each edge is stored both ways, so the node you just came from is always gray and every edge looks like a cycle. Undirected graphs need a different check (see below).
Variations
- Undirected graphs. Run an ordinary DFS or BFS, and a cycle exists when you reach an already-visited node that isn’t the one you just came from. With parallel edges, skip the edge id you arrived by, not the parent node. Or use union-find: an edge whose ends already have the same root closes a cycle.
- Linked lists, O(1) space. Floyd’s tortoise and hare moves one pointer one step and another two steps at a time. They meet if and only if there’s a loop; see linked lists.
- Kahn’s algorithm. Repeatedly remove nodes with no incoming edges, as in topological sort. If some nodes are never removed, there’s a cycle. It only says yes or no, but it’s easy to get right.
- Every node has one outgoing edge (a “functional graph”, like
x → f(x)). Walk from each node, colouring as you go, and stop at the first node you’ve seen before: gray means a new cycle, black means you joined an old one. - Safe nodes. A node is safe when no path from it reaches a cycle. With the same colouring, a node is safe exactly when its search turns it black without ever meeting a gray node.
Check yourself
5 quick questions. Pick an answer to see why it's right or wrong.
-
1
You must decide whether a set of build targets, each listing the targets it depends on, can be built at all. Which check is correct?
Only an edge back onto the current DFS path closes a directed loop. A single
visitedset and union-find both ignore direction, so two targets sharing a dependency (a diamond) would be reported as a cycle. BFS from one node also misses targets it can’t reach. Kahn’s algorithm with leftover nodes would be the other correct answer. -
2
This check uses a single
visitedset. What does it print?g = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}visited = set()def has_cycle(u):if u in visited:return Truevisited.add(u)return any(has_cycle(v) for v in g[u])print(has_cycle("a"))dis reached throughband marked visited, then reached again throughc, so the function says there’s a cycle. The graph is a diamond with no cycle. The fix is a separate on-path (gray) state that is cleared when a node finishes. -
3
What does this print?
WHITE, GRAY, BLACK = 0, 1, 2def cyclic(g):state = {u: WHITE for u in g}def dfs(u):state[u] = GRAYfor v in g[u]:if state[v] == GRAY:return Trueif state[v] == WHITE and dfs(v):return Truestate[u] = BLACKreturn Falsereturn any(state[u] == WHITE and dfs(u) for u in g)g1 = {1: [2, 3], 2: [3], 3: []}g2 = {1: [2], 2: [3], 3: [2], 4: [1]}print(cyclic(g1), cyclic(g2))In
g1, node 3 is reached twice, but the second time (from 1) it’s already black, so that’s not a cycle. Ing2, the search goes 1 → 2 → 3 and the edge 3 → 2 finds 2 still gray: a cycle, even though it doesn’t include the start node 1. -
4
Someone reuses a DFS on an undirected graph, stored with each edge in both adjacency lists: “if a neighbour is already visited, there’s a cycle”. What goes wrong?
Edge u–v is also in v’s list, so v immediately sees u as visited. Ignore the edge you came in on (by edge id, so that two parallel edges between the same pair still count as a cycle). Once that is fixed, one visited set is enough for undirected graphs: there are no one-way edges to fool it. Union-find is a simple alternative.
-
5
Kahn’s algorithm on a directed graph with 7 nodes outputs only 5 of them. What do you know about the 2 left over?
A node is left over when its indegree never reaches 0, which only happens when something upstream is stuck on a cycle. Nodes downstream of the cycle are stuck too, so the leftovers can be more than the cycle itself. Isolated nodes have indegree 0 and are output right away, and in a DAG the processing order never matters for whether every node comes out.