Cycle Detection (Graph)
The Intuition
Imagine hiking through a forest and dropping breadcrumbs to mark your trail. You're exploring paths, going deeper and deeper. If you round a corner and see your own breadcrumbs on the ground ahead of you, you've walked in a circle. That's cycle detection in its most basic form.
But you need to be more careful than just "visited or not." Picture three colors of breadcrumbs. White means you haven't been to that spot at all. Gray means your breadcrumbs are currently on the ground there, meaning it's part of the path you're actively walking right now. Black means you've fully explored that area on a previous hike, picked up your breadcrumbs, and moved on. You know every trail from that spot leads to dead ends or already-explored territory.
When you step onto a gray spot, you've found your own active trail. That's a cycle, a loop back to somewhere you're currently in the process of exploring. But when you step onto a black spot, there's no cause for alarm. Some earlier exploration already covered that area, and if it had a cycle, you would have found it then. The gray-versus-black distinction is why directed graphs need three colors. In an undirected graph, you can get away with just "visited or not" plus remembering who sent you to the current node (your parent), because an edge back to your parent isn't a real cycle, it's just the same road you walked in on.
When you finish exploring all paths from a node and backtrack, you change that node from gray to black. You're "picking up your breadcrumbs" because you're no longer on that path. Any future explorer who stumbles onto that black node knows it's fully charted territory. The gray nodes at any moment form your current DFS path from the root to where you're standing, and a back edge to any of them proves a cycle exists.
Deadlock detection, dependency validation, course prerequisite checking, detecting infinite loops in state machines, or identifying redundant edges in networks.
Need cycle length (need additional tracking), undirected graph with simple visited check (don't need 3 colors), or need to find ALL cycles (this finds existence only, use different algorithm).
Variations:
- 3-color DFS (directed): Colors nodes as unvisited, in-progress, or completed. A back edge to an in-progress node confirms a cycle.
- Parent tracking DFS (undirected): Tracks the parent of each node to avoid falsely flagging the edge back to the parent as a cycle.
- Union-Find (undirected): If two endpoints of an edge already share the same root, adding that edge creates a cycle.
- Topological sort check: If topological sort produces fewer than V nodes, the directed graph has a cycle.
- Graph with no edges (no cycle possible)
- Self-loop on a single node (cycle of length 1 in directed graphs)
- Graph with only two nodes and a bidirectional edge (not a cycle in undirected representation)
- Disconnected graph where only some components contain cycles
- Graph that is a single long chain (no cycle, but deep recursion)
- Multiple edges between the same pair of nodes (parallel edges form a cycle in undirected graphs)
- A directed graph where all nodes have exactly one outgoing edge (guaranteed to have a cycle)
Key Points
- •Directed graphs use 3-color DFS: white (unvisited), gray (in stack), black (done)
- •A back edge to a gray node proves a cycle exists in a directed graph
- •Undirected graphs track parent to distinguish tree edges from back edges
- •Union-Find can detect cycles in undirected graphs without DFS
- •Topological sort fails (fewer than V nodes in result) if a cycle exists
Code Template
1 def has_cycle_directed(graph, n):
2 """Detect cycle in a directed graph using 3-color DFS.
3 0 = white (unvisited), 1 = gray (in stack), 2 = black (done).
4 """
5 color = [0] * n
6
7 def dfs(u):
8 color[u] = 1 # mark as in-progress
9 for v in graph[u]:
10 if color[v] == 1:
11 return True # back edge found
12 if color[v] == 0 and dfs(v):
13 return True
14 color[u] = 2 # mark as completed
15 return False
16
17 for i in range(n):
18 if color[i] == 0 and dfs(i):
19 return True
20 return False
21
22 def has_cycle_undirected(graph, n):
23 """Detect cycle in an undirected graph using parent tracking."""
24 visited = [False] * n
25
26 def dfs(u, parent):
27 visited[u] = True
28 for v in graph[u]:
29 if not visited[v]:
30 if dfs(v, u):
31 return True
32 elif v != parent:
33 return True # back edge found
34 return False
35
36 for i in range(n):
37 if not visited[i] and dfs(i, -1):
38 return True
39 return False
40
41 def find_safe_nodes(graph, n):
42 """Find all nodes that do not lead to any cycle (eventual safe nodes).
43 Uses 3-color DFS: safe nodes are those that reach only black nodes.
44 """
45 color = [0] * n # 0=white, 1=gray, 2=black
46
47 def dfs(u):
48 color[u] = 1
49 for v in graph[u]:
50 if color[v] == 1:
51 return False
52 if color[v] == 0 and not dfs(v):
53 return False
54 color[u] = 2
55 return True
56
57 result = []
58 for i in range(n):
59 if color[i] == 0:
60 dfs(i)
61 if color[i] == 2:
62 result.append(i)
63 return resultCommon Mistakes
- Using parent tracking for directed graphs (it does not detect all directed cycles)
- Forgetting that an edge back to the parent is not a cycle in undirected graphs
- Not handling disconnected components (must start DFS from every unvisited node)
- Confusing cross edges with back edges in directed graph DFS