Cycle detection in directed graphs is a fundamental algorithmic problem with many real-world applications. A cycle exists when you can start from a node, follow directed edges, and eventually return to your starting point. This creates impossible situations in systems that require ordering or dependencies.
The most effective approach uses Depth-First Search (DFS) with state tracking. Unlike simple visited tracking, we need three states for each node:
The key insight is that a cycle exists if we encounter a "visiting" node during our DFS traversal. This means we've found a back edge - an edge that points to an ancestor in our current search path, creating a loop.
Why three states? Consider a diamond-shaped graph where node A connects to both B and C, and both B and C connect to D. When we finish exploring the B->D path and start exploring C->D, we don't want to mistake the already-visited D for a cycle. The "visited" state tells us this node was processed in a previous, completed path.
This algorithm runs in O(V + E) time, where V is the number of vertices and E is the number of edges, making it very efficient even for large graphs. The space complexity is O(V) for the recursion stack and state tracking.
1def has_cycle(graph):
2 states = {node: 0 for node in graph} # 0=unvisited, 1=visiting, 2=visited
3
4 def dfs(node):
5 states[node] = 1 # Mark as visiting
6
7 for neighbor in graph[node]:
8 if states[neighbor] == 1: # Back edge found!
9 return True
10 elif states[neighbor] == 0 and dfs(neighbor):
11 return True
12
13 states[node] = 2 # Mark as completely visited
14 return False
15
16 # Check all nodes (graph might be disconnected)
17 for node in graph:
18 if states[node] == 0 and dfs(node):
19 return True
20 return False