What Is DFS?#
Depth-First Search (DFS) explores a graph or tree by going as deep as possible down one path before backtracking and trying another.
Think of navigating a maze: you pick a corridor and walk until you hit a dead end, then backtrack to the last junction and try a different turn.
How It Works#
Starting from a source node:
- Mark the current node as visited
- Explore each unvisited neighbour recursively (or via a stack)
- When all neighbours are visited, backtrack
Implementation#
- Time Complexity: O(V + E), since it visits every vertex and edge once
- Space Complexity: O(V) for the recursion stack (or an explicit stack)
Interactive Lab#
Let's take the example in this visualization: six vertices A to F joined by nine edges, source A, target E. Press play and watch the stack rather than the graph. A pushes B and D; B is popped first and pushes C and E. Then C is popped, and every neighbour of C is already visited, so the frame returns with nothing to show for itself. That is the backtrack: the amber call-stack chain retracts to B before the traversal moves on and finds E.
DFS on Trees#
On a binary tree, DFS naturally produces three orderings based on when you process the root:
| Order | Process Root | Common Use |
|---|---|---|
| Pre-order | Before children | Copying a tree |
| In-order | Between children | Sorted output from BST |
| Post-order | After children | Deleting a tree, expression evaluation |
Key Applications#
- Cycle detection in directed/undirected graphs
- Topological sort (dependency ordering)
- Path finding between two nodes
- Connected components (counting isolated regions)
- Solving puzzles (mazes, Sudoku) via backtracking
DFS vs BFS: When to Use Which#
| Goal | Choose |
|---|---|
| Find any path | DFS (simpler code) |
| Find shortest path (unweighted) | BFS |
| Explore deep hierarchies (file system) | DFS |
| Level-by-level traversal | BFS |
What to Remember#
DFS is your go-to when you need to explore all reachable states. Its recursive nature maps cleanly onto tree/graph structures. Watch out for cycles in graphs: always track visited nodes.