BFS & DFS on Graphs and Grids — Complete Guide

Why BFS/DFS on Grids?

Grid problems model many real-world scenarios: connected components (islands), shortest paths, flood fill, and multi-source spread. The key insight is that a 2-D grid is just a graph where each cell connects to its 4 (or 8) neighbours.

The 7 Core Patterns

Pattern 1 — DFS Flood Fill (mark visited in-place)

Recurse into all 4 neighbours, mutating grid to avoid revisit.

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

Pattern 2 — BFS Shortest Path (layer-by-layer)

Use a deque; process layer by layer to get min distance.

from collections import deque
def bfs(grid, start):
    q = deque([(*start, 0)])   # (r, c, dist)
    visited = set([start])
    while q:
        r, c, d = q.popleft()
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < R and 0 <= nc < C and (nr,nc) not in visited:
                visited.add((nr,nc))
                q.append((nr, nc, d+1))

Pattern 3 — Multi-Source BFS (0-1 or all-at-once)

Push all sources at once; cells get updated with min distance from any source.

q = deque()
for r in range(R):
    for c in range(C):
        if grid[r][c] == '1':
            q.append((r, c))
            dist[r][c] = 0
# standard BFS from here

Pattern 4 — Connected Components (count islands)

Iterate all cells; each unvisited land cell starts a new component.

count = 0
for r in range(R):
    for c in range(C):
        if grid[r][c] == '1':
            dfs(grid, r, c)
            count += 1

Pattern 5 — Boundary DFS (mark non-enclosed, then flip)

Start from border cells; anything reachable from border cannot be enclosed.

for r in range(R):
    for c in range(C):
        if (r in (0, R-1) or c in (0, C-1)) and grid[r][c] == 'O':
            dfs_mark(grid, r, c, 'S')   # safe
for r in range(R):
    for c in range(C):
        if grid[r][c] == 'O': grid[r][c] = 'X'
        elif grid[r][c] == 'S': grid[r][c] = 'O'

Pattern 6 — 0-1 BFS (deque with 0-weight left push)

When edges have cost 0 or 1, use deque: push cost-0 to front, cost-1 to back.

from collections import deque
dq = deque([(0, 0, 0)])   # (dist, r, c)
dist = [[inf]*C for _ in range(R)]
dist[0][0] = 0
while dq:
    d, r, c = dq.popleft()
    if d > dist[r][c]: continue
    for dr, dc in dirs:
        nr, nc = r+dr, c+dc
        cost = 0 if same_color else 1
        if dist[r][c] + cost < dist[nr][nc]:
            dist[nr][nc] = dist[r][c] + cost
            if cost == 0: dq.appendleft((dist[nr][nc], nr, nc))
            else: dq.append((dist[nr][nc], nr, nc))

Pattern 7 — BFS with State (visited = cell + state)

When the graph has extra state (e.g. keys, parity), encode it in visited set.

visited = set()
q = deque([(sr, sc, 0)])   # 0 = no key
while q:
    r, c, keys = q.popleft()
    if (r, c, keys) in visited: continue
    visited.add((r, c, keys))
    # update keys when stepping on key cell

Complexity Reference

Pattern	Time	Space
DFS Flood Fill	O(R*C)	O(R*C) stack
BFS Shortest Path	O(R*C)	O(R*C)
Multi-Source BFS	O(R*C)	O(R*C)
Connected Components	O(R*C)	O(R*C)
Boundary DFS	O(R*C)	O(R*C)
0-1 BFS	O(R*C)	O(R*C)
BFS with State	O(RCS)	O(RCS)

5-Language BFS/DFS Templates

C — DFS Grid

void dfs(char** grid, int r, int c, int R, int C) {
    if (r<0||r>=R||c<0||c>=C||grid[r][c]!='1') return;
    grid[r][c]='0';
    dfs(grid,r+1,c,R,C); dfs(grid,r-1,c,R,C);
    dfs(grid,r,c+1,R,C); dfs(grid,r,c-1,R,C);
}

C++ — BFS Grid

void bfs(vector<vector<char>>& g, int r, int c) {
    queue<pair<int,int>> q;
    q.push({r,c}); g[r][c]='0';
    int dr[]={0,0,1,-1}, dc[]={1,-1,0,0};
    while (!q.empty()) {
        auto [x,y] = q.front(); q.pop();
        for (int i=0;i<4;i++) {
            int nx=x+dr[i], ny=y+dc[i];
            if (nx>=0&&nx<g.size()&&ny>=0&&ny<g[0].size()&&g[nx][ny]=='1') {
                g[nx][ny]='0'; q.push({nx,ny});
            }
        }
    }
}

Java — BFS Grid

private void bfs(char[][] grid, int r, int c) {
    int R = grid.length, C = grid[0].length;
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{r,c}); grid[r][c]='0';
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        for (int[] d : dirs) {
            int nr=cur[0]+d[0], nc=cur[1]+d[1];
            if (nr>=0&&nr<R&&nc>=0&&nc<C&&grid[nr][nc]=='1') {
                grid[nr][nc]='0'; q.add(new int[]{nr,nc});
            }
        }
    }
}

JavaScript — DFS Grid

function dfs(grid, r, c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
    if (grid[r][c] !== '1') return;
    grid[r][c] = '0';
    dfs(grid,r+1,c); dfs(grid,r-1,c);
    dfs(grid,r,c+1); dfs(grid,r,c-1);
}

Python — DFS Grid

def dfs(grid, r, c):
    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])): return
    if grid[r][c] != '1': return
    grid[r][c] = '0'
    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
        dfs(grid, r+dr, c+dc)

Problem Index

#	Problem	Pattern	Difficulty
01	Number of Islands	DFS Flood Fill	Easy
02	Flood Fill	DFS Flood Fill	Easy
03	Island Perimeter	Grid counting	Easy
04	Max Area of Island	DFS + area count	Medium
05	Surrounded Regions	Boundary DFS	Medium
06	Rotting Oranges	Multi-Source BFS	Medium
07	01 Matrix	Multi-Source BFS	Medium
08	Walls and Gates	Multi-Source BFS	Medium
09	Number of Enclaves	Boundary DFS	Medium
10	Count Sub Islands	DFS subset check	Medium
11	Making a Large Island	DFS + color map	Hard
12	Pacific Atlantic Water Flow	Two-source DFS	Medium
13	Shortest Path in Binary Matrix	BFS	Medium
14	As Far from Land as Possible	Multi-Source BFS	Medium
15	Word Search	DFS backtrack	Medium
16	Number of Distinct Islands	DFS + shape hash	Medium
17	Number of Closed Islands	Boundary DFS	Medium
18	Shortest Bridge	BFS + DFS	Medium
19	Minimum Effort Path	Binary search + BFS	Hard
20	Reachable Nodes in Subdivided Graph	BFS + math	Hard