Cycle Detection in Directed and Undirected Graphs
Cycle detection depends on edge direction. Directed graphs look for an edge into the active recursion path; undirected graphs must ignore the edge back to a node's parent or use disjoint sets to detect redundant connectivity.
Two Different Problems Sharing a Name
A cycle is a path that returns to its starting vertex. That definition sounds uniform, but detecting one in a directed graph and in an undirected graph are genuinely different problems requiring different algorithms — and using the wrong one produces confident, wrong answers.
In a directed graph a cycle needs the edges to agree on a direction: u → v → w → u. The edges v → u and u → v are unrelated, so having both is a legitimate two-cycle rather than a duplicate.
In an undirected graph every edge is traversable both ways, which creates an immediate difficulty. Walking from u to v and straight back to u revisits the start, and a naive detector calls that a cycle — but it is not. It is the same single edge traversed twice, and a genuine undirected cycle needs at least three distinct vertices.
So the undirected case must ignore the edge it arrived on, and the directed case must not. That single distinction is the source of most bugs in this area.
There is a second distinction worth stating early. In a directed graph, reaching an already-visited vertex does not imply a cycle at all — two different paths may simply converge on the same vertex, which is perfectly acyclic. What matters is whether the vertex is still being explored, and that requires tracking more than a boolean.
- Directed cycles require the edges to agree on direction
- Undirected cycles need three or more distinct vertices
- Undirected detection must skip the edge it arrived on
- Revisiting a vertex is not, by itself, evidence of a cycle
Directed Graphs: The Three Colours
The correct directed test uses DFS and classifies each vertex into one of three states rather than two.
White — not yet discovered. Grey — discovered and currently on the recursion stack, meaning its exploration has begun but not finished. Black — fully explored, with every descendant finished.
During the traversal, an edge to a grey vertex is a back edge: the search has looped round to a vertex still on the current path, which is precisely a cycle. An edge to a black vertex is harmless — that region is already complete, and reaching it again is just a second route in.
The theorem to state is exact: a directed graph contains a cycle if and only if a depth-first search finds a back edge. Nothing weaker suffices, and nothing stronger is needed.
Using a plain visited boolean conflates grey and black, so it reports a cycle whenever two paths converge — a false positive on perfectly valid DAGs. This is the single most common error in cycle detection code, and it passes any test whose graph happens to be a tree.
Implementation is a DFS that marks a vertex grey on entry, recurses into each neighbour, and marks it black on exit. The exit marking is what distinguishes the two non-white states, and forgetting it leaves everything grey forever, which reintroduces the false positives.
The complexity is O(V + E) with O(V) space for the colours plus the recursion stack. Since the recursion depth can reach V, a long chain risks stack overflow, and an iterative version is safer on deep graphs.
Kahn's algorithm offers an alternative with no recursion at all. Run a topological sort by repeatedly removing vertices of in-degree zero; if it emits fewer than V vertices, the remainder are waiting on one another and a cycle exists. Same O(V + E) cost, no stack risk, and the leftover vertices point directly at the offending cycle.
- White, grey, black — grey means still on the recursion stack
- An edge to a grey vertex is a back edge, hence a cycle
- A visited boolean reports cycles on valid DAGs
- Kahn's algorithm detects the same thing without recursion
Undirected Graphs: Parent Skipping and Union-Find
For undirected graphs the DFS is simpler, because there is no grey-versus-black distinction to make — but it needs one addition.
Run a DFS carrying the parent vertex through the recursion. When examining a neighbour: if it is unvisited, recurse into it passing the current vertex as parent; if it is already visited and is not the parent, a cycle exists.
The parent check is what prevents the immediate false positive. Every undirected edge appears in both endpoints' adjacency lists, so from v the edge back to u is always present — and without skipping it, every single edge registers as a cycle.
One subtlety catches people: skipping by parent vertex is correct only when the graph has no parallel edges. If two distinct edges join u and v, that genuinely is a cycle, and skipping by vertex identity misses it. Where parallel edges are possible, skip by edge identifier instead of by vertex.
Self-loops — an edge from a vertex to itself — are cycles by definition in both graph types, and should be tested for explicitly since neither the parent check nor the colour scheme necessarily catches them.
Union-find provides a different and often better approach for undirected graphs, particularly when edges arrive as a stream and the graph is never materialised. Initialise each vertex as its own component. For each edge (u, v), test whether find(u) == find(v): if they are already in the same component, this edge closes a cycle; otherwise union them and continue.
The cost is O(E · α(V)) — effectively linear — and the memory is two integer arrays with no adjacency structure at all. It also detects the cycle at the moment the closing edge arrives, which is exactly why Kruskal's algorithm uses it to reject cycle-forming edges while building a minimum spanning tree.
Union-find does not work for directed graphs, because merging components discards the direction information the directed problem depends on.
| Graph | Method | Cost | Detects by |
|---|---|---|---|
| Directed | Three-colour DFS | O(V + E) | An edge to a grey vertex |
| Directed | Kahn's algorithm | O(V + E) | Fewer than V vertices emitted |
| Undirected | DFS skipping the parent | O(V + E) | A visited non-parent neighbour |
| Undirected | Union-find | O(E·α(V)) | Both endpoints already joined |
| Linked list / functional | Floyd's tortoise and hare | O(n) time, O(1) space | The two pointers meet |
- Pass the parent down and skip it — every edge appears twice
- Skip by edge id, not vertex, when parallel edges are possible
- Union-find finds undirected cycles on a stream in near-linear time
- Union-find cannot be used on directed graphs
Directed colours and undirected union-find
def has_cycle(edges, n):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
a, b = find(u), find(v)
if a == b:
return True
parent[a] = b
return False
print("Cycle found:", has_cycle([(0, 1), (1, 2), (2, 0)], 3))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main() {
vector<int>p={0,1,2};
function<int(int)>f=[&](int x) {
return p[x]==x?x:p[x]=f(p[x]);
};
for(auto [u,v]:vector<pair<int,int>>{{0,1},{1,2},{2,0}}) {
u=f(u);
v=f(v);
if(u==v) {
cout<<"Cycle found: True";
return 0;
}
p[u]=v;
}
}class Main {
static int[]p={0,1,2};
static int f(int x) {
return p[x]==x?x:(p[x]=f(p[x]));
}
public static void main(String[]z) {
int[][]e={{0,1},{1,2},{2,0}};
for(int[]a:e) {
int u=f(a[0]),v=f(a[1]);
if(u==v) {
System.out.print("Cycle found: True");
return;
}
p[u]=v;
}
}
}Step through it
Running on undirected edges A–B, B–C, C–A
Read all 13 Steps
- Separate components Each vertex starts as its own root.
- Inspect A–B Process the first undirected edge.
- Find roots A and B have different representatives.
- Union A and B Accept the edge and merge their components.
- Inspect B–C Process B–C.
- Find roots again AB and C still have different roots.
- Union AB with C Accept and merge; A, B, C are now connected.
- Inspect C–A The final edge proposes another connection between C and A.
- Find root of C Path compression returns the shared component root.
- Find root of A A returns that same root.
- Roots match An existing path A–B–C already connects the endpoints.
- Reject the edge Adding C–A would close the cycle, so union-find rejects it.
- Report cycle For directed graphs, use white/gray/black DFS and report an edge to gray.
Boundaries, and What to Return
Several details decide whether an implementation is right on real input.
Disconnected graphs. A cycle may lie in a component your traversal never enters, so the search must be restarted from every unvisited vertex. Running once from vertex 0 is the standard omission and it silently misses cycles.
Self-loops are cycles and need an explicit check. Parallel edges are cycles in undirected graphs and require edge-based rather than vertex-based parent skipping.
A DAG has no cycles by definition — the acyclicity is what the A stands for. So 'detect a cycle in a DAG' is a trick phrasing; the answer is that there is none, and the real question is usually whether a given directed graph is a DAG.
What to return deserves a deliberate decision, because a boolean is usually the least useful answer. A build system reporting 'circular dependency detected' is far less helpful than one reporting 'A → B → C → A'. Both methods can produce the witness: the three-colour DFS has the cycle sitting on its recursion stack from the grey vertex down, and Kahn's leftover vertices contain it.
Some problems want the count of cycles, or all cycles, and those are substantially harder — enumerating all simple cycles is exponential in the worst case, since a complete graph has factorially many. Detecting existence is linear; enumerating is not, and conflating the two leads to an algorithm that never terminates on dense input.
A separate case worth knowing: linked lists and functional graphs, where every vertex has exactly one outgoing edge. There, Floyd's tortoise and hare detects a cycle in O(1) space by advancing one pointer at one step and another at two. If a cycle exists, the fast pointer enters it and closes the gap by exactly one node per iteration, so a meeting is guaranteed rather than merely likely. Resetting one pointer to the start after they meet and advancing both singly locates the cycle's entry point.
That constant-space property is why Floyd's is the expected answer for linked lists, where a hash set of visited nodes would work but costs O(n) memory.
- Restart from every unvisited vertex or miss whole components
- Detecting existence is linear; enumerating all cycles is exponential
- Return the cycle's vertices, not just a boolean
- Floyd's algorithm gives O(1) space on single-successor graphs