Cycle Detection with DFS
What you'll learn: How to use Depth-First Search to detect cycles in both directed and undirected graphs by classifying the edges you encounter.
The Core Idea
When DFS traverses a graph, it discovers different types of edges based on where they lead. By recognizing certain edge patterns, you can detect whether a cycle exists without explicitly tracing the entire loop.
Think of it like exploring a mansion: if you walk down a hallway and suddenly find a door that leads back to a room you're currently inside (not just one you visited earlier), you've discovered a loop in the building's layout.
How It Works
For undirected graphs, a cycle exists if during DFS you encounter an edge leading to an already-visited node that isn't your immediate parent. Since edges go both ways, you need to ignore the edge you just came from.
For directed graphs, a cycle exists if you encounter a back edge—an edge pointing to a node that's currently in your DFS recursion stack (still being explored). This indicates you've circled back to an ancestor in the DFS tree.
Implementation Pattern
# Undirected graph cycle detection
def has_cycle_undirected(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent: # Back to non-parent = cycle
return True
return False
return any(dfs(node, -1) for node in graph if node not in visited)
The key difference for directed graphs: track nodes in the current path (recursion stack) separately from globally visited nodes.
Key Takeaway: Cycle detection with DFS relies on edge classification—finding back edges in directed graphs or non-parent edges to visited nodes in undirected graphs signals a cycle.