Pattern visualizer

Detect Cycle in Directed Graph

In an undirected graph, reaching an already-visited node is enough to declare a cycle. A directed graph needs one more bit per node, because two separate paths can legitimately converge on the same target without looping — that is a cross-edge, not a cycle. The fix is to track which nodes are ACTIVE right now, meaning still open on the current DFS call path, versus DONE, meaning fully explored and safe to converge on. A cycle exists exactly when an edge points at a node that is still active — a back-edge into your own ancestry. Animated on: 7 vertices with directed edges 0->1, 1->2, 2->3, 2->6, 3->4, 4->5, 5->3 — does the graph contain a cycle?.

DFS with three colours: unseen, active (on the call stack), done

time O(V + E)space O(V)step 1 / 15

Vertices and directed edges

line 1

7 vertices and 7 directed edges. A cycle means some node can reach itself by following arrows forward — DFS finds one the moment it revisits a node that is still open on its own current path.

Pseudocode

1FUNCTION hasCycle(n, edges):
2  BUILD adjacency list next FROM edges
3  color <- ARRAY of n zeros
4  FOR u FROM 0 TO n - 1
5    IF color[u] = 0 AND dfs(u, next, color) = true
6      RETURN true
7  RETURN false
8FUNCTION dfs(u, next, color):
9  color[u] <- 1
10  FOR EACH v IN next[u]
11    IF color[v] = 1
12      RETURN true
13    IF color[v] = 0 AND dfs(v, next, color) = true
14      RETURN true
15  color[u] <- 2
16  RETURN false

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap