Depth-first search (DFS) explores a graph by going as deep as possible along each branch before backtracking. While BFS expands level by level like a wavefront, DFS dives down a single path until it hits a dead end, then backs up and tries the next path. This aggressive exploration strategy makes DFS the foundation for many interview problems.

Recursive DFS Template

DFS maps naturally to recursion. The call stack acts as the implicit data structure that tracks where to backtrack to:

1def dfs(graph, vertex, visited):
2    visited.add(vertex)
3    # process vertex here
4
5    for neighbor in graph[vertex]:
6        if neighbor not in visited:
7            dfs(graph, neighbor, visited)

This is the simplest form. You mark the vertex as visited, process it, then recursively visit each unvisited neighbor. When all neighbors of a vertex have been visited, the function returns, effectively backtracking to the previous vertex.

Iterative DFS with a Stack

You can replace the recursion with an explicit stack. This avoids stack overflow on deep graphs and gives you more control:

1def dfs_iterative(graph, start):
2    visited = set()
3    stack = [start]
4
5    while stack:
6        vertex = stack.pop()
7        if vertex in visited:
8            continue
9        visited.add(vertex)
10        # process vertex here
11
12        for neighbor in graph[vertex]:
13            if neighbor not in visited:
14                stack.append(neighbor)

Note the difference from BFS: replace the queue (FIFO) with a stack (LIFO). This single change transforms breadth-first into depth-first. The stack version processes neighbors in the opposite order compared to the recursive version (last neighbor pushed is first popped), but both are valid DFS traversals.

DFS vs BFS: When to Use Which

Use BFS when:

• You need the shortest path in an unweighted graph
• You need to process vertices level by level
• The graph is wide but shallow (BFS uses O(width) memory)

Use DFS when:

• You need to explore all paths (backtracking problems)
• You need to detect cycles
• You need topological ordering
• The graph is deep but narrow (DFS uses O(depth) memory)
• The problem involves connected components

Time and Space Complexity

Time: O(V + E), same as BFS. Each vertex is visited once, and each edge is examined once.

Space: O(V) for the visited set, plus O(V) for the recursion stack (or explicit stack) in the worst case. The worst case is a linear graph (like a linked list) where the stack depth equals V.

DFS on Grids

Just like BFS, DFS works on grids with implicit adjacency:

1def dfs_grid(grid, row, col, visited):
2    rows, cols = len(grid), len(grid[0])
3    if row \< 0 or row >= rows or col \< 0 or col >= cols:
4        return
5    if (row, col) in visited:
6        return
7    visited.add((row, col))
8    # process cell
9
10    for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
11        dfs_grid(grid, row + dr, col + dc, visited)

This is the pattern for "flood fill" and "number of islands" problems. Start DFS from an unvisited cell, mark all reachable cells as visited. Each DFS call explores one connected component.