Course contentsShow
← Computer Science
Lesson 373 of 2,8729. Stacks and QueuesFree lesson

Depth-First Search with Explicit Stack

Implement iterative DFS using a stack instead of recursion for graph traversal.

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

  1. Push the starting node onto your stack
  2. 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
  3. 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.