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.
Why directed and undirected cycles differ
In a directed graph, reaching any previously visited vertex does not prove a cycle: it may be a completed branch. Three colours separate white unvisited vertices, gray active calls, and black completed calls. Only an edge to gray returns to an ancestor on the current directed path.
An undirected adjacency list stores each edge twice. DFS therefore sees the edge back to its parent immediately; treating that as a cycle is a false positive. A visited neighbor different from the parent closes a genuine alternate route.
- Direction changes the invariant
- Gray identifies the active path
- Ignore the undirected parent edge
Three-colour DFS
Mark a vertex gray on entry. Recurse through white neighbors, report a cycle on a gray neighbor, and mark the vertex black only after all outgoing edges finish. Keeping parents allows reconstruction from the back-edge endpoint to its ancestor.
This method is O(V+E) and naturally works across disconnected directed graphs when DFS restarts from every white vertex. It also forms the cycle-checking half of DFS-based topological sorting.
- White → gray → black
- A gray edge proves a directed cycle
- Parents recover the cycle path
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;}}}undirected edges A–B, B–C, C–ACycle found: TrueRun the example step by step
Union-find for undirected edge streams
Start with every vertex in its own set. For each undirected edge (u,v), compare roots. Different roots are merged; equal roots mean u and v already have a path, so the new edge closes a cycle and must be rejected.
With union by size or rank and path compression, M operations cost O(M α(V)) amortized, effectively constant for practical inputs. Union-find detects existence but does not directly return the cycle path; parent-aware DFS is better when the actual vertices are required.
- Same root means redundant connectivity
- Union by rank controls height
- Path compression accelerates later finds
Self-loops, parallel edges, and DAGs
A self-loop is immediately a cycle in both directed and undirected graphs. Two parallel undirected edges form a length-two multigraph cycle, although a simple-graph problem may forbid parallel edges. State the graph model before deciding how to treat them.
A directed graph without cycles is a DAG and admits a topological order. Kahn's algorithm offers another cycle test: if zero-indegree processing removes fewer than V vertices, the leftover subgraph is cyclic. Choose the method according to whether you need an order, a witness path, or online undirected insertions.
- Self-loops are cycles
- Graph model controls parallel-edge handling
- Kahn detects leftover directed cycles
Common implementation failures
A single boolean visited array cannot distinguish a directed back edge from an edge to completed work. Likewise, union-find is not a general directed-cycle algorithm because connectivity ignores orientation. Match the stored state to the proof the algorithm needs.
For recursive DFS, deep chains can overflow the call stack; explicit frames preserve the color invariant safely. For union-find, call find before comparing roots and merge roots rather than raw vertices. These details are correctness requirements, not micro-optimizations.
- Directed DFS needs three states
- Union-find is for undirected connectivity
- Merge component roots
Choosing the output contract
Decide whether the caller needs a boolean, one cycle, every cyclic component, or the vertices whose values are affected by cycles. A boolean implementation may return at the first witness; reconstructing a directed cycle needs predecessor links from the gray endpoint back to the ancestor. In an undirected DFS, storing both the current vertex and its parent prevents the reverse copy of a tree edge from being reported as a witness.
For dynamic undirected edge insertion, union-find answers whether a new edge creates a cycle efficiently, but deletions require more advanced dynamic-connectivity structures. For directed dependency graphs, colors or Kahn's leftover count are appropriate. Test a tree, a DAG with cross edges, a disconnected graph with one cyclic component, a self-loop, and parallel edges under the chosen graph model. State whether the returned cycle repeats its first vertex at the end.
- Output needs determine stored state
- Parent links recover witnesses
- Dynamic deletion is beyond ordinary union-find