15. BFS — Breadth-First Search

What you'll learn

• 1Implement BFS with a deque
• 2Compute shortest distances
• 3Handle multi-source BFS

Overview

BFS visits all nodes at distance 1 before any at distance 2, and so on. This level-by-level expansion makes the first time we reach a node also the shortest path in an unweighted graph.

Core Concepts

1. BFS template

from collections import deque

def bfs(start):
    visited = [False] * (n + 1)
    dist = [-1] * (n + 1)
    q = deque([start])
    visited[start] = True
    dist[start] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

2. Grid BFS

DR = (-1, 1, 0, 0)
DC = (0, 0, -1, 1)

def bfs_grid(start_r, start_c):
    R, C = len(grid), len(grid[0])
    visited = [[False] * C for _ in range(R)]
    dist = [[-1] * C for _ in range(R)]
    q = deque([(start_r, start_c)])
    visited[start_r][start_c] = True
    dist[start_r][start_c] = 0
    while q:
        r, c = q.popleft()
        for dr, dc in zip(DR, DC):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and grid[nr][nc] != WALL:
                visited[nr][nc] = True
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

3. Multi-source BFS

Start BFS from multiple sources simultaneously. Enqueue all sources at distance 0.

q = deque()
for src in sources:
    q.append(src)
    dist[src] = 0
# ... rest of BFS proceeds identically

4. DFS vs BFS

Examples

Example 1 — src/01_bfs_basic.py

BFS on adjacency list, printing distances.

Example 2 — src/02_bfs_grid.py

Shortest path in a maze.

Example 3 — src/03_multi_source.py

Multi-source BFS — e.g. 'time for tomatoes to ripen' (BOJ 7576).

Example 4 — src/04_path_reconstruct.py

Track parents to reconstruct the actual shortest path, not just its length.

Common Mistakes

1. list.pop(0) instead of deque.popleft() — turns O(n) BFS into O(n²).
2. Marking visited on dequeue → same node enqueued many times → TLE.
3. Forgetting BFS doesn't work for weighted graphs (use Dijkstra).
4. Storing 2D coordinates as strings 'r,c' instead of tuples — slower.

Recap

• BFS = deque + visited array.
• Mark visited on enqueue.
• Gives shortest path in unweighted graphs only.

Try It

1. BOJ 2178 (Maze exploration).
2. BOJ 7576 (Tomatoes) — multi-source BFS.
3. BOJ 1697 (Hide and seek) — BFS on integer line.