Depth-First Search (DFS) — Algorithm & Applications

Imagine you're exploring a vast cave system. You stand at the entrance with multiple tunnels branching before you. One approach is to fully explore the first tunnel—following it as far as it goes, exploring every sub-tunnel before returning—before moving to the next. This is the essence of Depth-First Search (DFS): commit fully to one path before backtracking.

DFS is one of the two fundamental graph traversal algorithms (alongside Breadth-First Search), yet it holds a special place in computer science. Its elegant recursive structure maps directly onto the call stack, making it intuitive to implement. Its iterative version reveals the explicit stack mechanics that power recursive algorithms. And its applications span from detecting cycles in dependency graphs to topological sorting in build systems.

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Given a starting vertex, DFS visits a vertex, then recursively visits all vertices reachable from it through unvisited edges, before returning to explore other branches.

The core principle: Go deep before going wide.

This contrasts with Breadth-First Search (BFS), which explores all neighbors at the current level before moving deeper. DFS commits to following one path completely—like a determined explorer who refuses to turn around until hitting a dead end.

Formal Definition:

Given a graph G = (V, E) and a starting vertex s, DFS systematically explores the graph by:

1. Visiting the starting vertex s
2. For each unvisited neighbor u of the current vertex v:
   • Recursively apply DFS starting from u
3. When all neighbors have been visited, backtrack to the previous vertex

This simple rule generates a traversal that visits every vertex reachable from s exactly once.

Why "Depth-First"?

The name captures the algorithm's defining characteristic: it prioritizes depth over breadth. When multiple unvisited neighbors exist, DFS doesn't systematically explore all neighbors before proceeding—it picks one and dives deeper immediately.

Consider a tree structure:

       A
      /|
     B C D
    /|   |
   E F   G

Starting from A, DFS might visit: A → B → E → F → C → D → G

Notice how it fully explores B's subtree (E, F) before moving to C, then fully explores D's subtree (G). Each subtree is completely traversed before sibling subtrees are considered.

Key Insight: The Traversal Forms a Spanning Tree

As DFS explores, the edges it traverses form a DFS spanning tree (or forest, if the graph is disconnected). This tree structure is not arbitrary—it encodes the discovery relationships: for any vertex v, all vertices discovered from v form the subtree rooted at v. This property is foundational to many DFS applications.

The recursive implementation of DFS is remarkably elegant—it mirrors the algorithm's natural definition almost verbatim. The system call stack implicitly tracks where we've been, eliminating the need for explicit stack management.

Core Recursive Structure:

DFS(vertex v):
    mark v as visited
    process v (if desired)
    for each neighbor u of v:
        if u is not visited:
            DFS(u)

That's it. The recursion handles backtracking automatically—when a DFS call completes (no more unvisited neighbors), the call returns and the previous call continues from where it left off.

Why Recursion Maps So Naturally

DFS has an inherently recursive structure:

• Base case: A vertex with no unvisited neighbors (dead end)
• Recursive case: Visit each unvisited neighbor, fully exploring its subtree

This maps perfectly to function calls: each recursive call explores a subtree, and returning from the call naturally backtracks to the parent.

Step-by-Step Execution Trace

Let's trace through the recursive DFS on our example graph, showing the call stack at each step:

Graph:
   A ── B ── E
   |    |
   C    F
   |
   D ── G

Final traversal order: A → B → E → F → C → D → G

While recursive DFS is elegant, it relies on the implicit call stack. The iterative version makes this stack explicit, giving us direct control over memory usage and eliminating recursion depth limits.

Core Insight: Replace Recursion with an Explicit Stack

Every recursive algorithm can be converted to an iterative one using an explicit stack data structure. In recursive DFS:

• The call stack stores the sequence of vertices we've visited but haven't fully explored
• Returning from a call is equivalent to popping from the stack

In iterative DFS, we manage this stack ourselves:

Iterative-DFS(vertex start):
    create empty stack S
    push start onto S
    
    while S is not empty:
        v = pop from S
        if v is not visited:
            mark v as visited
            process v
            for each neighbor u of v:
                if u is not visited:
                    push u onto S

Subtle Difference: Traversal Order

The iterative version may produce a slightly different traversal order than the recursive version. Why? The recursive version processes neighbors in their listed order (first neighbor first). The iterative version pushes all neighbors onto the stack, so the last neighbor pushed is processed first (LIFO behavior).

To achieve identical order, push neighbors in reverse order.

Detailed Stack Trace: Iterative DFS Execution

Let's trace the iterative version step by step:

Final traversal: A → B → E → F → C → D → G

(Same as recursive version because we pushed neighbors in reverse order)

Both implementations achieve the same goal—visiting all reachable vertices in depth-first order—but differ in important ways. Understanding these differences helps you choose the right approach for each situation.

Handling Pre-order and Post-order in Iterative DFS

Recursive DFS naturally supports both pre-order (process before children) and post-order (process after children) actions:

def dfs_recursive(v):
    pre_order_action(v)  # Before exploring children
    for child in children(v):
        dfs(child)
    post_order_action(v)  # After all children explored

In iterative DFS, pre-order is straightforward (process when popping), but post-order requires explicitly tracking when all children have been processed. A common technique is to push a "marker" or use state flags:

def dfs_with_postorder(start):
    stack = [(start, False)]  # (vertex, is_processed_flag)
    
    while stack:
        vertex, processed = stack.pop()
        
        if processed:
            post_order_action(vertex)
            continue
        
        pre_order_action(vertex)
        stack.append((vertex, True))  # Push back with flag = True
        
        for child in reversed(children(vertex)):
            if not visited(child):
                stack.append((child, False))

This technique is essential for applications like topological sorting that rely on post-order.

DFS can operate on any graph representation, but the choice affects both implementation details and performance. Let's examine DFS across the three common representations.

1. Adjacency List (Most Common)

This is the standard representation for DFS. Each vertex stores a list of its neighbors, allowing O(degree(v)) iteration over neighbors.

# Adjacency List: {vertex: [neighbor1, neighbor2, ...]}
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

Total DFS complexity: O(V + E) — We visit each vertex once, and for each vertex, we iterate over its adjacency list. The sum of all adjacency list lengths equals 2E (for undirected) or E (for directed).

2. Adjacency Matrix

Matrix representation uses M[i][j] = 1 to indicate an edge from i to j.

# Adjacency Matrix: matrix[i][j] = 1 if edge (i,j) exists
matrix = [
    [0, 1, 1, 0],  # A's connections
    [1, 0, 0, 1],  # B's connections
    [1, 0, 0, 0],  # C's connections
    [0, 1, 0, 0]   # D's connections
]

Total DFS complexity: O(V²) — For each vertex, we scan the entire row (V entries) to find neighbors. This is inefficient for sparse graphs.

3. Edge List

Edge list stores edges as pairs (u, v). This representation is space-efficient but requires preprocessing for efficient DFS.

# Edge List: [(u, v), ...]
edges = [('A', 'B'), ('A', 'C'), ('B', 'D')]

Direct DFS on edge list: O(V × E) — For each vertex, scan all edges to find neighbors.

Better approach: Convert to adjacency list first (O(E)), then run standard DFS (O(V + E)). Total: O(V + E).

def edge_list_to_adj_list(edges):
    graph = {}
    for u, v in edges:
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)  # For undirected
    return graph

Let's put everything together with a complete, production-quality DFS implementation that handles common edge cases and provides both recursive and iterative versions.

We've established a deep understanding of DFS mechanics. Let's consolidate the key insights:

What's Next:

With the DFS algorithm firmly understood, we'll explore its core mechanism: stack-based exploration. The next page examines how the stack determines traversal order, why DFS naturally produces certain orderings, and how this stack behavior enables powerful applications like backtracking and topological sorting.