Depth-First Search with Explicit Stack
You'll learn how to traverse a graph depth-first using a stack data structure instead of recursion.
The Core Idea
Depth-First Search (DFS) explores a graph by going as deep as possible down one path before backtracking. Traditionally, DFS uses recursion, which relies on the implicit call stack. But you can also implement DFS iteratively using an explicit stack that you control directly.
Think of exploring a maze: recursion is like having a magical guide who remembers your entire path automatically. An explicit stack is like dropping breadcrumbs yourself—you manually track where you've been and what to explore next.
Why Use an Explicit Stack?
- Avoid stack overflow: Deeply nested recursion can crash; iterative DFS won't
- More control: You manage the stack directly
- Same logic: The traversal order matches recursive DFS
How It Works
- Push the starting node onto your stack
- While the stack isn't empty:
- Pop a node
- If it's unvisited, mark it visited and process it
- Push all its unvisited neighbors onto the stack
- Repeat until the stack is empty
The stack holds nodes "waiting" to be explored. By using a stack (LIFO), you always explore the most recently discovered path first—that's the "depth-first" behavior.
Example Walk-Through
Imagine nodes A→B, A→C, B→D:
- Push A, pop A (visit), push C then B
- Pop B (visit), push D
- Pop D (visit)
- Pop C (visit)
- Stack empty—done!
Key Takeaway: Iterative DFS replaces the recursive call stack with an explicit stack you manage, giving you the same depth-first traversal with more control and no recursion limits.