DFS Iterative Implementation with Stack
What You'll Learn
You'll learn how to implement Depth-First Search using an explicit stack data structure instead of relying on function call recursion.
Why Use a Stack for DFS?
In the previous lesson, you saw DFS implemented recursively. Behind the scenes, recursion uses the call stack to remember where to return after exploring deeply. We can replicate this behavior explicitly using our own stack data structure, giving us more control and avoiding potential stack overflow issues with very deep graphs.
The Core Idea
Instead of letting recursive function calls manage the exploration order, we:
- Push the starting vertex onto a stack
- Pop a vertex, mark it visited, and process it
- Push all its unvisited neighbors onto the stack
- Repeat until the stack is empty
Think of it like exploring a maze with a pile of sticky notes. Each note says "check this path next." You always grab the top note (most recent), explore that direction, and add new notes for unexplored branches you find.
Basic Implementation Pattern
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop() # Get most recent
if vertex not in visited:
visited.add(vertex)
print(vertex) # Process vertex
# Push neighbors (they'll be explored deeply)
for neighbor in graph[vertex]:
if neighbor not in visited:
stack.append(neighbor)
The stack ensures we explore deeply before backtracking—the same traversal order as recursive DFS.
Key Takeaway: Iterative DFS replaces the implicit recursion call stack with an explicit stack data structure, maintaining the depth-first exploration pattern while giving you direct control over the traversal process.