Graph AlgosAlgorithmaka detect cycle in graph, back edge detection

Cycle Detection

Decide whether a graph has a cycle: three-colour DFS for directed graphs; DFS with parent tracking or union-find for undirected graphs.

▶ VisualizePattern: Depth-First SearchPractice (3)
Progress

Overview

Cycle detection asks whether a graph contains a closed walk with no repeated edges. The answer technique depends on whether edges are directed, because the definition of a "back edge" differs.

Directed: run Depth-First Search (DFS) with three colours. White = unvisited, grey = on the current recursion path, black = finished. An edge to a grey vertex is a back edge to an ancestor and closes a directed cycle. An edge to a black vertex is harmless (a forward or cross edge). This is the same machinery as DFS Topological Sort; equivalently, Kahn's Algorithm reports a cycle when fewer than n vertices are emitted.

Undirected: every edge u — v is seen twice (from u and from v), so a plain "visited" check would report a cycle for any edge. Instead, during DFS an edge from u to an already-visited v is a cycle unless v is the vertex we came from (parent[u]). Alternatively, process edges with Union-Find (Disjoint Set Union): an edge whose endpoints are already in the same set closes a cycle. That is the tool of choice when edges arrive incrementally or the graph is given as an edge list.

directedundirectedDFSunion-findback edgeO(V + E)

Intuition

A mental model before the formal terms.

Directed: you are following one-way corridors, leaving a lit lamp in every room you are currently *inside* (your path of open doors) and switching it off when you back out. Stepping into a room whose lamp is lit means you have walked in a loop. Stepping into a dark room you have already finished is fine — you only reach it again from a different direction, and everything beyond it was already explored without finding a lit lamp.

Undirected: walking on a two-way trail, every path you take can be walked straight back. So bumping into the trail marker you *just* laid does not count — that is merely turning around. Bumping into any older marker means you reached a known spot by a genuinely different route: a loop.

Union-find view: each edge you add either joins two islands (no cycle) or adds a second bridge between islands already joined — that second bridge together with the old route is a cycle.

How it works

  1. Directed, three colours: for each white vertex run dfs(u): colour grey; for each v in adj[u]: grey → return "cycle"; white → recurse; black → skip. Colour black on exit.
  2. Directed, Kahn: compute in-degrees, peel sources; if the count of emitted vertices < n, a cycle exists (see Kahn's Algorithm).
  3. Undirected, DFS parent check: dfs(u, parent): mark visited; for each v in adj[u]: if not visited, recurse with parent u; else if v != parent, a cycle exists. With multi-edges, compare edge *ids* rather than parent vertices, otherwise a double edge u — v is missed.
  4. Undirected, union-find: for each edge (u, v): if find(u) == find(v) there is a cycle (that edge is redundant); else union(u, v). Total O(E α(V)).
  5. To *return* the cycle in the DFS variants, keep parent[] and, on finding the back edge u → v, walk from u up the parent chain to v.

Why it works

Directed: a grey vertex v is an ancestor of u in the DFS tree, so a tree path v ⇝ u exists; the edge u → v closes it into a cycle. Conversely, if a cycle exists, let c be the first cycle vertex DFS discovers; every other cycle vertex is reached while c is grey (they are reachable from c through cycle edges and nothing on the cycle finishes before c), so the cycle edge into c is scanned while c is grey.

Black neighbours cannot indicate a cycle: everything reachable from a black vertex has finished, so there is no path from it back to any grey vertex (that grey vertex would have finished earlier).

Undirected: in a DFS of an undirected graph every non-tree edge is a back edge to an ancestor (there are no cross edges), so any visited neighbour other than the parent is an ancestor and closes a cycle with the tree path.

Union-find: components are trees exactly as long as every added edge joined two different components; the first edge inside one component creates the first cycle.

Recognition

How to tell a problem wants this.

  • "Is this dependency graph consistent / can all tasks be completed?" — directed cycle check.
  • "Which edge can be removed to make this a tree?" (Redundant Connection) — union-find on undirected edges.
  • "Is the graph a tree / forest?" — undirected: no cycle and (for a tree) connected with n - 1 edges.
  • Deadlock detection in a wait-for graph, circular imports, reference cycles — directed.
“connected groups” → Depth-First Search“prerequisites” → Topological Sort“connected groups” → Union-Find

Interactive visualization

Play, step, change the input. ← → and space work too.

ABCDEFGH
Gray path
empty
1/6Three-color DFS: white = unseen, gray = on the current path, black = finished. A directed cycle exists exactly when DFS meets an edge into a gray node.
Current nodeGray: on the current DFS pathBlack: fully exploredTree edgeBack edge (closes a cycle)
PseudocodeLearn Cycle Detection →
1color[v] = WHITE for all v
2def dfs(u):
3  color[u] = GRAY   # on the current path
4  for v in neighbors(u):
5    if color[v] == GRAY: return cycle (back edge u→v)
6    if color[v] == WHITE and dfs(v): return true
7  color[u] = BLACK; return false
8for u in nodes: if color[u] == WHITE and dfs(u): report cycle
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1# directed
2color[*] = WHITE
3dfs(u): color[u] = GRAY
4  for v in adj[u]: if color[v] == GRAY: return true; if WHITE and dfs(v): return true
5  color[u] = BLACK; return false
6# undirected
7dfs(u, parent): visited[u] = true
8  for v in adj[u]: if !visited[v]: if dfs(v, u): return true
9                  else if v != parent: return true
10  return false

Implementations

1# Cycle detection splits by graph kind. Directed graphs need the three-colour
2# DFS (a back edge into the *active path*); undirected graphs need only a
3# visited set plus a parent check, because every edge looks like a 2-cycle.
4 
5 
61 · Directed: an edge into a vertex still on the DFS path closes a cycle
7def has_cycle_directed(out: list[list[int]]) -> bool:
8    n = len(out)
9    state = [0] * n  # 0 = new, 1 = on the path, 2 = finished
10    for s in range(n):
11        if state[s] != 0:
12            continue
13        stack = [[s, 0]]
14        state[s] = 1
15        while stack:
16            frame = stack[-1]
17            u, i = frame[0], frame[1]
18            if i < len(out[u]):
19                frame[1] += 1
20                v = out[u][i]
21                if state[v] == 1:
22                    return True  # back edge
23                if state[v] == 0:
24                    state[v] = 1
25                    stack.append([v, 0])
26            else:
27                state[u] = 2
28                stack.pop()
29    return False
30 
31 
322 · Undirected: any edge to a visited non-parent vertex closes a cycle
33def has_cycle_undirected(adj: list[list[int]]) -> bool:
34    n = len(adj)
35    seen = [False] * n
36    for s in range(n):
37        if seen[s]:
38            continue
39        stack = [(s, -1)]  # (vertex, parent)
40        seen[s] = True
41        while stack:
42            u, parent = stack.pop()
43            for v in adj[u]:
44                if v == parent:
45                    continue  # the edge we arrived on, not a cycle
46                if seen[v]:
47                    return True
48                seen[v] = True
49                stack.append((v, u))
50    return False
51 
52 
533 · Undirected via union-find: an edge inside one component closes a cycle
54def has_cycle_union_find(n: int, edges: list[tuple[int, int]]) -> bool:
55    parent = list(range(n))
56 
57    def find(x: int) -> int:
58        while parent[x] != x:
59            parent[x] = parent[parent[x]]
60            x = parent[x]
61        return x
62 
63    for u, v in edges:
64        a, b = find(u), find(v)
65        if a == b:
66            return True
67        parent[b] = a
68    return False
69 
70 
714 · Floyd's tortoise and hare finds a cycle in a functional graph
72def find_cycle_start(nxt: list[int], start: int) -> int:
73    slow = fast = start
74    while True:
75        slow = nxt[slow]
76        fast = nxt[nxt[fast]]
77        if slow == fast:
78            break
795 · Reset one pointer to the start; they meet at the cycle entrance
80    slow = start
81    while slow != fast:
82        slow = nxt[slow]
83        fast = nxt[fast]
84    return slow
Walkthrough
  1. The directed version uses mutable *list* frames so frame[1] += 1 advances the cursor; the undirected version uses immutable tuples because it pops immediately and needs no cursor.
  2. u, parent = stack.pop() unpacks the tuple in one statement.
  3. find is a closure over parent, which keeps the union-find variant compact without a class.
  4. slow = fast = start chains the assignment, and the while True with an internal break is the Python spelling of do...while, which the language does not have.
  5. Floyd needs constant space and works on any structure with a "next" operation, which is why it is the linked-list answer rather than a set of seen nodes.
Complexity (this implementation)
time O(V + E) for both DFS variants; O(E α(V)) for union-find; O(n) for Floyd · space O(V) for DFS and union-find; O(1) for Floyd
Language notes
  • Python has no do...while, so while True: with a trailing if ...: break is the standard equivalent — needed here because both pointers start equal.
  • The directed frame must be a list; a tuple would raise TypeError on the cursor increment. The undirected frame can stay a tuple because it is never modified.
  • networkx.find_cycle raises NetworkXNoCycle when there is none, and handles both directed and undirected graphs.
  • Closures capturing a mutable list (parent) work without nonlocal, because the list is mutated rather than rebound.
Common mistakes in this language
  • Translating do...while as a plain while slow != fast, which never executes because the pointers start equal.
  • Using a tuple for the directed DFS frame and hitting TypeError on the increment.
  • Rebinding parent inside find (rather than mutating it), which would need nonlocal and is a sign the logic has drifted.
Language differences that matter here
  • Python is the only one of the four without a do...while, which matters here because Floyd's algorithm genuinely needs one — while True plus break is the workaround.
  • Mutable versus immutable stack frames: the directed DFS needs a mutable frame everywhere (C++ reference binding, JS/TS object, Python list), while the undirected version can use an immutable pair in all four.
  • Recursion is avoided in every language, but for different limits: RecursionError near 1000 frames in CPython, RangeError near 10000 in JS engines, and a silent stack overflow in C++.
  • Library support: Python has networkx.find_cycle and graphlib (which raises CycleError); C++ has Boost.Graph visitors; JS/TS have neither.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Union-find on an edge list: O(E α(V)) time, O(V) space; stops at the first cycle edge.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Validating dependency graphs, detecting deadlocks, checking that constraints are satisfiable (directed).
  • Checking whether an undirected graph is a forest / tree, or finding the one redundant edge.
  • As a guard before algorithms that require a DAG (Topological Sort, DP on DAGs) or a tree.
Avoid it when
  • You need the *shortest* or *smallest-weight* cycle — that is a different (harder) problem, usually BFS from each vertex or Floyd-Warshall.
  • You need all cycles enumerated — exponential in general; think again about the problem.
  • Directed graph handed as an edge list only and you reach for union-find — union-find ignores direction and answers the wrong question for directed graphs.

Alternatives

DFS Topological SortKahn's AlgorithmUnion-Find (Disjoint Set Union)Strongly Connected Components

Common mistakes

  • Using a single visited flag in a directed graph: a cross edge to a finished vertex is misreported as a cycle (e.g. 0→1, 0→2, 1→2 has no cycle).
  • Omitting the parent check in an undirected graph: every edge is then "seen twice" and reported as a cycle.
  • Using a parent-*vertex* check with multi-edges: two parallel edges u — v form a cycle but are skipped; compare edge ids instead.
  • Applying union-find to a directed graph.
  • Only running DFS from vertex 0 — cycles in other components are missed.

Interview patterns

  • Course Schedule: directed cycle check is the whole problem.
  • Redundant Connection: union-find; the first edge whose endpoints are already connected is the answer.
  • Graph Valid Tree: no undirected cycle and exactly n - 1 edges (or: connected and n - 1 edges).
  • Find Eventual Safe States: vertices whose DFS finishes black without hitting grey.
Interview questions on this
Mock interviews

Example problems

Number of Connected ComponentsmediumRedundant ConnectionmediumCourse Schedulemedium