Depth-First Search Algorithm Overview

👋 Welcome Gophers! In this lesson, we are going to be covering the Depth-First Search algorithm and how it works conceptually.

Overview

Now that we’ve covered sorting algorithms, let’s dive into graph traversal. Depth-First Search (DFS) is one of the most fundamental algorithms for exploring graphs and trees.

Think of DFS like exploring a maze—you go as deep as possible down one path before backtracking and trying another. It’s called “depth-first” because we prioritize going deep over going wide.

How It Works

DFS uses a stack (either explicit or implicit through recursion) to manage which nodes to visit next. Here’s the basic flow:

Start at your source node and mark it as visited
For each unvisited neighbor, recursively visit it (or push it onto a stack)
When you’ve explored all neighbors, backtrack to try other branches
Continue until all reachable nodes have been visited

The beauty of DFS is its simplicity—especially when using recursion. The call stack naturally handles the “stack” for you.

Recursive vs Iterative

You can implement DFS two ways:

Recursive: Super clean and intuitive. Just call the function on each neighbor, and the call stack manages everything for you.

Iterative: You manually maintain a stack and loop through nodes. More control, and you avoid potential stack overflow issues on massive graphs.

Traversal Orders

When working with trees specifically, DFS gives you three different orderings depending on when you process each node:

Preorder: Process node → then children (great for copying trees)
Inorder: Left child → node → right child (perfect for BSTs to get sorted output)
Postorder: Children → then node (useful for deletion and cleanup operations)

Time and Space Complexity

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges. We visit every node and edge exactly once.
Space Complexity: O(V) for the recursion stack or explicit stack in the worst case.

Visual Example

Here’s how DFS explores a sample graph, with numbers showing the order of visits:

<svg viewBox="0 0 600 350" xmlns="http://www.w3.org/2000/svg">
  <!-- Background -->
  <rect width="600" height="350" fill="#1a1a2e"/>

  <!-- Title -->
  <text x="300" y="30" text-anchor="middle" fill="#00d9ff" font-size="18" font-weight="bold">
    Depth-First Search Traversal Order
  </text>

  <!-- Start node (Node 0) - Red -->
  <circle cx="100" cy="100" r="25" fill="#ff6b6b" stroke="#00d9ff" stroke-width="2"/>
  <text x="100" y="107" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">0</text>

  <!-- Node 1 - Cyan (visited early) -->
  <circle cx="220" cy="60" r="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
  <text x="220" y="67" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">1</text>

  <!-- Node 2 - Cyan (visited early) -->
  <circle cx="220" cy="160" r="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
  <text x="220" y="167" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">2</text>

  <!-- Node 3 - Light teal (visited deeper) -->
  <circle cx="360" cy="80" r="25" fill="#45b7aa" stroke="#00d9ff" stroke-width="2"/>
  <text x="360" y="87" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">3</text>

  <!-- Node 4 - Light teal (visited deeper) -->
  <circle cx="360" cy="180" r="25" fill="#45b7aa" stroke="#00d9ff" stroke-width="2"/>
  <text x="360" y="187" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">4</text>

  <!-- Node 5 - Pale (visited last) -->
  <circle cx="500" cy="130" r="25" fill="#95e1d3" stroke="#00d9ff" stroke-width="2"/>
  <text x="500" y="137" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">5</text>

  <!-- Edges with arrows -->
  <defs>
    <marker id="arrowhead" markerWidth="10" markerHeight="10" refX="9" refY="3" orient="auto">
      <polygon points="0 0, 10 3, 0 6" fill="#666"/>
    </marker>
  </defs>

  <!-- Edge 0 -> 1 -->
  <line x1="120" y1="85" x2="200" y2="70" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>

  <!-- Edge 0 -> 2 -->
  <line x1="120" y1="115" x2="200" y2="150" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>

  <!-- Edge 1 -> 3 -->
  <line x1="245" y1="65" x2="335" y2="80" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>

  <!-- Edge 2 -> 4 -->
  <line x1="245" y1="155" x2="335" y2="185" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>

  <!-- Edge 3 -> 5 -->
  <line x1="380" y1="95" x2="480" y2="120" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>

  <!-- Edge 4 -> 5 -->
  <line x1="380" y1="165" x2="480" y2="140" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>

  <!-- Legend -->
  <text x="50" y="280" fill="#00d9ff" font-size="13" font-weight="bold">Traversal Path:</text>
  <text x="50" y="305" fill="#a8dadc" font-size="12">0 → 1 → 3 → 5 → (backtrack) → 4 → (backtrack) → 2</text>

  <text x="50" y="335" fill="#888" font-size="11">Red = Start | Teal = Early visit | Light = Later visit</text>
</svg>

Notice the pattern: we go deep first (0 → 1 → 3 → 5), then backtrack to explore other branches (4, then 2).

When to Use DFS

DFS is perfect for:

Topological sorting of directed acyclic graphs
Detecting cycles in directed and undirected graphs
Finding connected components in a graph
Backtracking problems like mazes, puzzles, and Sudoku solvers
Tree traversals and tree transformations
Detecting strongly connected components in directed graphs

Quiz Time

Validate what you’ve learned in this lesson by attempting these quiz questions: