PATTERN 12 OF 22

Graphs (BFS/DFS)

Traverse and search graphs using BFS and DFS. Master grid traversal, connected component counting, multi-source BFS, graph cloning, and shortest-path finding on implicit graphs.

Time: O(V + E) for adjacency list, O(rows × cols) for grids

Space: O(V) for visited set + queue/stack

Learn & Reference

Understanding the Pattern

Graphs (BFS/DFS) Pattern

A graph is a set of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, multiple connected components, and nodes with any number of connections. Graphs are everywhere in interviews — grids, social networks, word transformations, and dependency chains are all graph problems in disguise.

Core Concept

Graphs come in two common representations:

Adjacency List

Each node stores a list of its neighbors. This is the standard for sparse graphs (few edges relative to nodes).

0: [1, 2]
1: [0, 3]
2: [0]
3: [1]

Grid (2D Matrix)

A grid is an implicit graph where each cell is a node and edges connect to 4-directional (or 8-directional) neighbors. Most interview graph problems use grids.

Grid:        Implicit graph:
1 1 0        (0,0)─(0,1)
1 0 0        │
0 0 1        (1,0)      (2,2)

The two fundamental traversal strategies — DFS and BFS — apply to both representations.

Key Techniques

1. DFS on Grids (Flood Fill)

DFS explores as deep as possible before backtracking. On a grid, this means picking a direction and following it until you hit a boundary or visited cell, then backtracking. DFS is ideal for counting connected components (like islands) and computing component properties (like area).

function dfs(grid, row, col):
    if out of bounds or already visited or not target: return
    mark (row, col) as visited
    dfs(grid, row+1, col)  // down
    dfs(grid, row-1, col)  // up
    dfs(grid, row, col+1)  // right
    dfs(grid, row, col-1)  // left

2. BFS on Grids (Level-by-Level)

BFS explores all neighbors at distance 1, then distance 2, etc. This guarantees shortest path in unweighted graphs. Use BFS when you need the minimum number of steps.

queue = [(startRow, startCol)]
visited = set()
while queue:
    row, col = queue.popleft()
    for each neighbor (nr, nc):
        if valid and not visited:
            visited.add((nr, nc))
            queue.append((nr, nc))

3. Multi-Source BFS

Start BFS from multiple sources simultaneously by putting them all in the queue at the start. This computes the minimum distance from any source to every cell. Classic use case: rotting oranges spreading simultaneously.

queue = [all initial sources]  // multiple start points
while queue:
    process level by level
    each source spreads one step per level

4. Visited Tracking

Unlike trees, graphs can have cycles. You must track visited nodes to avoid infinite loops. Three common approaches:

Separate visited set/array: Clean, doesn't modify input
Modify the grid in-place: Mark cells as visited by changing their value (e.g., 1 → 0)
Node coloring: For adjacency list graphs, store visited state per node

5. DFS/BFS on Adjacency List Graphs

Same algorithms, different neighbor access:

// DFS on adjacency list
function dfs(node, visited, graph):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited, graph)

Common Mistakes

Forgetting the visited check — Without marking nodes as visited, DFS/BFS loops forever on graphs with cycles. This is the #1 graph bug.
Not handling disconnected components — A single BFS/DFS only reaches nodes connected to the start. For problems like "count islands," you need to loop over all nodes and start a new traversal for each unvisited one.
Off-by-one in grid bounds — Always check 0 <= row < rows && 0 <= col < cols before accessing grid[row][col]. Forgetting this causes index-out-of-bounds errors.
Mutating input when you shouldn't — Modifying the grid as a visited marker is efficient but destructive. If the problem needs the original grid later, use a separate visited structure.
Using DFS when BFS is needed — DFS does NOT give shortest path in an unweighted graph. If the problem asks for minimum steps/distance, you must use BFS.

When to Use

You see a **grid/matrix** and need to find connected regions, shortest paths, or spread patterns

The problem involves **connected components** (counting islands, groups, clusters)

You need the **shortest path** in an unweighted graph (BFS)

The problem describes **spreading/propagation** over time (multi-source BFS)

You need to **traverse all reachable nodes** from a starting point

The problem involves an **implicit graph** (e.g., word transformations where words are nodes)

You need to **clone** or **copy** a graph structure

Template

1# Grid DFS Template — Count connected components
2def solve(grid):
3    if not grid:
4        return 0
5    rows, cols = len(grid), len(grid[0])
6    count = 0
7
8    def dfs(r, c):
9        if r < 0 or r >= rows or c < 0 or c >= cols:
10            return
11        if grid[r][c] != 1:
12            return
13        grid[r][c] = 0  # mark visited
14        dfs(r + 1, c)
15        dfs(r - 1, c)
16        dfs(r, c + 1)
17        dfs(r, c - 1)
18
19    for r in range(rows):
20        for c in range(cols):
21            if grid[r][c] == 1:
22                count += 1
23                dfs(r, c)
24
25    return count

{ }

Syntax Reference

1# Queue for BFS
2from collections import deque
3q = deque()
4q.append(item)        # enqueue
5item = q.popleft()    # dequeue
6len(q)                # size
7bool(q)               # non-empty check
8
9# Visited set
10visited = set()
11visited.add((row, col))
12(row, col) in visited  # O(1) lookup
13
14# 4-directional neighbors
15directions = [(0,1),(0,-1),(1,0),(-1,0)]
16for dr, dc in directions:
17    nr, nc = row + dr, col + dc
18    if 0 <= nr < rows and 0 <= nc < cols:
19        # process (nr, nc)

📋

Common Recipes

1# Recipe 1: Grid DFS — Count Connected Components (Islands)
2def count_components(grid):
3    rows, cols = len(grid), len(grid[0])
4    count = 0
5    def dfs(r, c):
6        if r < 0 or r >= rows or c < 0 or c >= cols:
7            return
8        if grid[r][c] != 1:
9            return
10        grid[r][c] = 0  # mark visited
11        dfs(r+1, c); dfs(r-1, c)
12        dfs(r, c+1); dfs(r, c-1)
13    for r in range(rows):
14        for c in range(cols):
15            if grid[r][c] == 1:
16                count += 1
17                dfs(r, c)
18    return count
19
20# Recipe 2: Grid BFS — Shortest Path
21from collections import deque
22def shortest_path(grid, start, end):
23    rows, cols = len(grid), len(grid[0])
24    q = deque([(start[0], start[1], 0)])
25    visited = {(start[0], start[1])}
26    while q:
27        r, c, dist = q.popleft()
28        if (r, c) == (end[0], end[1]):
29            return dist
30        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
31            nr, nc = r+dr, c+dc
32            if 0 <= nr < rows and 0 <= nc < cols:
33                if (nr, nc) not in visited and grid[nr][nc] == 0:
34                    visited.add((nr, nc))
35                    q.append((nr, nc, dist+1))
36    return -1
37
38# Recipe 3: Multi-Source BFS
39from collections import deque
40def multi_source_bfs(grid, sources):
41    rows, cols = len(grid), len(grid[0])
42    q = deque()
43    visited = set()
44    for r, c in sources:
45        q.append((r, c, 0))
46        visited.add((r, c))
47    while q:
48        r, c, dist = q.popleft()
49        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
50            nr, nc = r+dr, c+dc
51            if 0 <= nr < rows and 0 <= nc < cols:
52                if (nr, nc) not in visited:
53                    visited.add((nr, nc))
54                    q.append((nr, nc, dist+1))
55
56# Recipe 4: Adjacency List BFS
57from collections import deque
58def bfs(graph, start):
59    visited = {start}
60    q = deque([start])
61    while q:
62        node = q.popleft()
63        for neighbor in graph[node]:
64            if neighbor not in visited:
65                visited.add(neighbor)
66                q.append(neighbor)

O(n)

Complexity

Operation	Time	Space	Notes
DFS traversal	O(V + E)	O(V)	V = vertices, E = edges; space for recursion stack + visited
BFS traversal	O(V + E)	O(V)	Space for queue + visited
Grid DFS/BFS	O(R × C)	O(R × C)	R = rows, C = cols; visits each cell once
Multi-source BFS	O(R × C)	O(R × C)	Same as single-source BFS
Build adjacency list	O(V + E)	O(V + E)	One pass over edges

Watch Out

✗Forgetting the visited check — Without marking nodes as visited, DFS/BFS loops forever on graphs with cycles. This is the #1 graph bug.
✗Not handling disconnected components — A single BFS/DFS only reaches nodes connected to the start. For problems like "count islands," you need to loop over all nodes and start a new traversal for each unvisited one.
✗Off-by-one in grid bounds — Always check `0 <= row < rows && 0 <= col < cols` before accessing `grid[row][col]`. Forgetting this causes index-out-of-bounds errors.
✗Mutating input when you shouldn't — Modifying the grid as a visited marker is efficient but destructive. If the problem needs the original grid later, use a separate visited structure.
✗Using DFS when BFS is needed — DFS does NOT give shortest path in an unweighted graph. If the problem asks for minimum steps/distance, you must use BFS.

PRACTICE PROBLEMS

Heaps / Priority Queues

Backtracking