Cycle Detection in Directed and Undirected Graphs
Detect cycles in undirected graphs with parent tracking and in directed graphs with DFS color-coding (white/grey/black three-state visited).
Why Cycle Detection Matters
A cycle in a graph is a path that starts and ends at the same node. Cycle detection is critical in many algorithms: topological sort fails on cyclic graphs, dependency resolution must detect circular dependencies, and deadlock detection in OS scheduling requires finding cycles in resource-allocation graphs. The approach differs between undirected and directed graphs — they require fundamentally different algorithms.
from collections import defaultdict
# Undirected cycle: A-B-C-A (triangle)
undirected = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
undirected[u].append(v)
undirected[v].append(u)
# Directed cycle: A->B->C->A
directed = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
directed[u].append(v) # one direction only
# Key difference:
# Undirected: edge A-B appears as both A->B and B->A
# Must track parent to distinguish cycle from back-edge to parent
print('Undirected and directed cycles need different detection')Undirected Cycle Detection with DFS
In an undirected graph, a cycle exists if DFS visits a node that is already in the current path (not just visited). The challenge: every edge appears in both directions, so when we visit a child node, its neighbour list includes our current node (the parent). We must track the parent of each node to avoid falsely flagging the edge back to the parent as a cycle. If we encounter a visited node that is not our parent, we've found a cycle.
def has_cycle_undirected(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
if dfs(nb, node): # recurse with current as parent
return True
elif nb != parent: # visited and not parent = CYCLE
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1): # -1 = no parent for root
return True
return False
print(has_cycle_undirected(4, [(0,1),(1,2),(2,3),(3,1)])) # True
print(has_cycle_undirected(3, [(0,1),(1,2)])) # FalseAll lessons in this course
- Graph Representations and Traversal Setup
- BFS: Shortest Path and Level Traversal
- DFS: Connected Components and Flood Fill
- Cycle Detection in Directed and Undirected Graphs