DFS on Directed vs Undirected Graphs
What you'll learn: How DFS behaves differently when traversing directed versus undirected graphs, especially in edge classification and cycle detection.
Core Differences
When running DFS, the graph type fundamentally changes how we interpret edges during traversal. While the algorithm's structure stays the same, the meaning of what we discover differs dramatically.
In undirected graphs, every edge is bidirectional. When DFS visits node A and explores neighbor B, it later sees A again from B's perspective. This creates back edges that aren't necessarily cycles—they're just the "return path" of the edge you already traversed. A cycle exists only when a back edge leads to an ancestor other than the immediate parent.
In directed graphs, edges have direction. When DFS explores from A to B, there's no automatic return path. Back edges here always indicate a true cycle. The edge classification becomes more nuanced: you get forward edges (shortcuts to descendants), cross edges (between separate subtrees), and back edges (to ancestors, proving cycles).
Practical Impact
Cycle detection differs:
- Undirected: Check if a back edge leads to a non-parent node
- Directed: Any back edge confirms a cycle immediately
Edge classification:
- Undirected: Tree edges and back edges only
- Directed: Tree, back, forward, and cross edges possible
Think of it like hiking trails: On an undirected trail, you can walk both ways—seeing the path you came from isn't surprising. On a directed trail (one-way streets), spotting a route that loops back is significant—it's a real cycle.
Key Takeaway: DFS on directed graphs provides richer edge classification and simpler cycle detection, while undirected graphs require tracking parent nodes to avoid false cycle positives from bidirectional edges.