On this page
Description
Does the graph loop back on itself? For a build system, a cycle means modules that can't be compiled in any order. For a network, it's a physical loop that circulates broadcasts forever. A traversal answers the question, but "I've been here before" means different things in undirected and directed graphs. This skill covers both checks, plus Kahn's algorithm, which finds directed cycles without recursion.
We'll go from simple to more technical:
- The pattern: the parent check (undirected) and three-state DFS (directed).
- A second flavor: Kahn's algorithm, where the nodes it can't take reveal a cycle.
- Where cycle checks run in production (builds, deadlocks, spreadsheets, networks).
- What breaks it: the wrong meaning of "visited", resetting finished nodes, and missing components.
The approach
Java
// Undirected: a visited neighbor that isn't the node we came from closes a cycle
boolean bfsHasCycle(int start, List<List<Integer>> adj, boolean[] visited) {
Deque<int[]> queue = new ArrayDeque<>(); // {node, parent}
queue.add(new int[]{start, -1});
visited[start] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int node = cur[0], parent = cur[1];
for (int next : adj.get(node)) {
if (!visited[next]) { visited[next] = true; queue.add(new int[]{next, node}); }
else if (next != parent) return true; // reached again by a different route
}
}
return false;
}
// Directed: only an edge back to a node still on the current path closes a cycle
boolean dfs(int node, List<List<Integer>> adj, int[] state) { // 0 = unvisited, 1 = in progress, 2 = done
state[node] = 1;
for (int next : adj.get(node)) {
if (state[next] == 1) return true; // back edge: next is an ancestor on this path
if (state[next] == 0 && dfs(next, adj, state)) return true;
}
state[node] = 2; // finished - safe to reach again later
return false;
}
// Either check covers one component; loop over every unvisited node to cover the graph
for (int v = 0; v < n; v++) if (state[v] == 0 && dfs(v, adj, state)) return true;
Python
from collections import deque
# Undirected: a visited neighbor that isn't the node we came from closes a cycle
def bfs_has_cycle(start: int, adj: list[list[int]], visited: list[bool]) -> bool:
queue = deque([(start, -1)]) # (node, parent)
visited[start] = True
while queue:
node, parent = queue.popleft()
for nxt in adj[node]:
if not visited[nxt]:
visited[nxt] = True
queue.append((nxt, node))
elif nxt != parent:
return True # reached again by a different route
return False
# Directed: only an edge back to a node still on the current path closes a cycle
def dfs(node: int, adj: list[list[int]], state: list[int]) -> bool: # 0 unvisited, 1 in progress, 2 done
state[node] = 1
for nxt in adj[node]:
if state[nxt] == 1:
return True # back edge: nxt is an ancestor on this path
if state[nxt] == 0 and dfs(nxt, adj, state):
return True
state[node] = 2 # finished - safe to reach again later
return False
# Either check covers one component; loop over every unvisited node to cover the graph:
# any(state[v] == 0 and dfs(v, adj, state) for v in range(n))
Undirected adjacency lists store every edge both ways, so the node you just came from is always "visited" - that's the edge you walked, not a cycle. Directed graphs have the opposite problem: two paths can legitimately converge on the same node (A->B->D and A->C->D), so "visited" isn't a cycle either. What closes a directed cycle is an edge back to a node whose DFS hasn't finished yet - an ancestor on the current path - which is exactly what the "in progress" state marks.
A second flavor: count what Kahn's algorithm can't take
A directed graph is acyclic exactly when all its nodes can be put in a topological order. Kahn's algorithm (repeatedly take a node with no remaining incoming edges) finds such an order - and it gets stuck on cycles, because every node on a cycle keeps an incoming edge from the cycle itself:
Java
int[] indegree = new int[n];
for (List<Integer> next : adj) for (int v : next) indegree[v]++;
Deque<Integer> ready = new ArrayDeque<>();
for (int v = 0; v < n; v++) if (indegree[v] == 0) ready.add(v);
int taken = 0;
while (!ready.isEmpty()) {
int u = ready.poll();
taken++;
for (int v : adj.get(u)) if (--indegree[v] == 0) ready.add(v);
}
boolean hasCycle = taken < n; // the nodes left over are on a cycle or depend on one
Python
from collections import deque
indegree = [0] * n
for targets in adj:
for v in targets:
indegree[v] += 1
ready = deque(v for v in range(n) if indegree[v] == 0)
taken = 0
while ready:
u = ready.popleft()
taken += 1
for v in adj[u]:
indegree[v] -= 1
if indegree[v] == 0:
ready.append(v)
has_cycle = taken < n # the nodes left over are on a cycle or depend on one
No recursion, so no stack-depth limit. On 0->1, 1->2, 2->1, 2->3 it takes only node 0: nodes 1 and 2 wait on each other forever, and 3 waits on 2.
Where you'll see it
Build tools and package managers reject circular dependencies before building anything; databases detect deadlocks by finding a cycle in the "transaction waits for transaction" graph; spreadsheet engines flag circular references; network switches run spanning-tree protocols precisely because an undirected loop would circulate broadcasts forever.
Which tool for which job?
| You need | Use |
|---|---|
| A cycle in an undirected graph | BFS or DFS with a parent check |
| A cycle in a directed graph | three-state DFS: a back edge to an in-progress node |
| Directed, no recursion, plus an order | Kahn's algorithm: fewer than n taken means a cycle |
| The cycle's nodes | DFS, walking parents back from the back edge |
| Undirected edges arriving one at a time | union-find: an edge inside one set closes a cycle |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Undirected, plain "visited" | every edge comes back as a false cycle | skip the parent |
| Directed, plain "visited" | a diamond looks like a cycle | three states: in progress vs done |
| Resetting finished nodes to unvisited | exponential re-exploration (1,048,575 calls vs 39) | mark them done |
| Checking from node 0 only | a cycle in another component is missed | loop over every unvisited node |
| Treating Kahn's leftovers as the cycle | dependents of the cycle are included | find the cycle with DFS |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. In an undirected graph, why isn't "I reached a visited node" enough to report a cycle?
Show answer
Every undirected edge is stored in both endpoints' lists, so right after walking from A to B, B's list shows A as visited - that's the same edge, not a cycle. Only a visited neighbor other than the parent means the node was reached by a second route.
2. Why does a directed check need three states instead of visited/unvisited?
Show answer
A visited node might be finished (reached before along another branch - fine, as in a diamond) or still on the current path (an ancestor - a cycle). "In progress" marks the current path; "done" marks finished nodes that can be reached again safely.
3. Kahn's algorithm takes only 1 of 4 nodes. What does that tell you?
Show answer
The graph has a cycle. Nodes on a cycle always keep an incoming edge from the cycle, so their in-degree never reaches zero; nodes that depend on them get stuck too. Any graph where Kahn's takes all n nodes is acyclic.
Key takeaways
- Undirected: a visited neighbor other than the parent closes a cycle - the parent is just the edge you walked.
- Directed: only an edge to a node still in progress (on the current path) closes a cycle; three states tell "ancestor" from "finished".
- Mark finished nodes "done", not "unvisited", or they're re-explored exponentially often.
- Kahn's algorithm detects directed cycles without recursion: fewer than n nodes taken means a cycle.
- Loop over every unvisited node - a cycle can hide in any component.