BFS vs DFS: When to Use Which (With Real Examples)

Graph traversal comes down to one question: do you explore wide or deep first? That's it. BFS goes level by level. DFS goes as far down one path as possible before backtracking. The trick is knowing which one your problem actually needs.

The Core Difference

BFS (Breadth-First Search) uses a queue. You visit a node, enqueue all its neighbors, then process them in FIFO order. This means you explore all nodes at distance 1 before any node at distance 2. DFS (Depth-First Search) uses a stack (or recursion, which is just the call stack). You visit a node, pick one neighbor, go deep into that path, and only backtrack when you hit a dead end.

# BFS — iterative with queue
from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

# DFS — iterative with stack
def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                stack.append(neighbor)
    return visited

Look at how similar the code is. Swap a queue for a stack (or popleft() for pop()) and you've switched algorithms. That's not a coincidence — both are just systematic ways to visit every reachable node.

When BFS Wins

BFS guarantees the shortest path in an unweighted graph. Since it explores level by level, the first time it reaches a node, that's the minimum number of edges from the source.

This makes BFS the right choice for:

• Shortest path in a maze — each cell is a node, edges connect adjacent cells. BFS from the start gives you the minimum steps to the exit.
• Word ladder problems — "change one letter at a time from COLD to WARM." Each word is a node, edges connect words that differ by one letter. BFS finds the shortest transformation sequence.
• Minimum moves in a game — chess knight minimum moves, minimum button presses, etc.

If the problem says "minimum," "shortest," or "fewest" and the graph is unweighted, reach for BFS first.

When DFS Wins

DFS is better for problems that need exhaustive exploration or that have a natural recursive structure:

• Number of islands — classic grid problem. For each unvisited land cell, DFS flood-fills the entire island, marking cells as visited. Count how many times you trigger a new DFS.
• Cycle detection — DFS with a "currently in stack" set detects back edges, which indicate cycles.
• Topological sort — process a node only after all its dependencies. DFS post-order gives you a reverse topological ordering.
• Path existence — "is there ANY path from A to B?" DFS works fine and uses less memory than BFS on deep, narrow graphs.

DFS also tends to use less memory on graphs that are wide but not deep, since the stack only holds nodes along the current path.

Adjacency List vs Adjacency Matrix

You need to represent the graph before you traverse it. Two main options:

Adjacency list — a dictionary (or array of lists) where each node maps to its neighbors.

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

Adjacency matrix — a 2D array where matrix[i][j] = 1 means there's an edge from i to j.

matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0]
]

For most interview problems, use an adjacency list. It's more space-efficient for sparse graphs (which most real-world graphs are), and iterating over neighbors is O(degree) instead of O(V). The matrix is better when you need O(1) edge lookup or the graph is dense.

The Island Problem — A DFS Classic

This shows up everywhere in interviews. Given a 2D grid of 1s (land) and 0s (water), count the number of islands.

def num_islands(grid):
    if not grid:
        return 0

rows, cols = len(grid), len(grid[0])
    count = 0

def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # mark visited
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

return count

Each DFS call sinks an entire island. The number of times we start a fresh DFS is the island count. Simple, clean, and runs in O(rows * cols).

Shortest Path in a Maze — A BFS Classic

Given a grid where 0 is open and 1 is a wall, find the shortest path from top-left to bottom-right.

from collections import deque

def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(0, 0, 1)])  # row, col, distance
    visited = {(0, 0)}

while queue:
        r, c, dist = queue.popleft()
        if r == rows - 1 and c == cols - 1:
            return dist
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

return -1  # no path

The first time BFS reaches the destination, that distance is guaranteed to be minimal. No need to explore further.

Quick Decision Framework

Ask yourself:

1. Need shortest path (unweighted)? → BFS
2. Need to explore all possibilities? → DFS
3. Need topological order? → DFS
4. Need cycle detection? → DFS (with state tracking)
5. Need level-by-level processing? → BFS
6. Memory constrained, deep graph? → Iterative DFS

Both run in O(V + E) time. The difference is in what problems they solve naturally.

If you want to practice these patterns hands-on with immediate feedback, CodeUp has interactive graph problems where you can trace through BFS and DFS step by step — way more effective than just reading about them.