Cycle Detection
DSA · Graphs
Theory
In an undirected graph a cycle exists if DFS reaches an already-visited vertex that is not the parent it came from. In a directed graph, DFS tracks three states: unvisited, on the current path, and finished; reaching a vertex that is still on the current path means a cycle. Union-find can also detect cycles in undirected graphs by checking whether an edge joins two vertices already in the same set.
Why we use it
Cycles break dependency ordering (circular imports, deadlocks) and must be detected before scheduling tasks.
When to use it
Use it to validate task or course prerequisites, detect deadlocks, check that a graph is a tree, and in build systems.
How it works
- DFS with states: unvisited, visiting, done
- Mark u as visiting
- For each neighbour v
- v is visiting? Yes: Cycle found. No: If unvisited, DFS(v).
- Mark u done; no cycle if DFS finishes
Syntax
Directed (three colours):
state[v] = 1 (on path)
for nb in graph[v]:
if state[nb] == 1: cycle!
if state[nb] == 0: dfs(nb)
state[v] = 2 (done)Example
def has_cycle(graph):
state = {v: 0 for v in graph} # 0 new, 1 on path, 2 done
def dfs(v):
state[v] = 1
for nb in graph[v]:
if state[nb] == 1:
return True
if state[nb] == 0 and dfs(nb):
return True
state[v] = 2
return False
for v in graph:
if state[v] == 0 and dfs(v):
return True
return False
courses_ok = {"SQL": ["Python"], "Python": ["Spark"], "Spark": []}
courses_bad = {"A": ["B"], "B": ["C"], "C": ["A"]}
print("Valid plan has cycle:", has_cycle(courses_ok))
print("Circular plan has cycle:", has_cycle(courses_bad))Key points
- Undirected: visited neighbour that is not the parent
- Directed: neighbour still on the current path
- Union-find also works for undirected graphs
- Needed before topological sorting