Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes layer by layer, visiting all neighbors at the current depth before moving deeper. It’s the go-to technique for finding shortest paths in unweighted graphs and grids, and it appears constantly in LeetCode Medium problems.

New to BFS? The core idea is simple: use a queue to explore nodes level by level – process all nodes at distance 1, then distance 2, then distance 3, and so on. The first time you reach a node is always the shortest path.

BFS explores a graph level by level A B C D E Level 0 Level 1 Level 2 Queue: [A] Process A → enqueue B, C Queue: [B, C] Process B → enqueue D, E Process C → E already visited Queue: [D, E] Process D, E → no new neighbors Queue: [] → Done! Level 0 (start) Level 1 Level 2

Contents

Basic BFS

When to use: The problem says “shortest path” or “minimum steps” in an unweighted graph, or asks you to explore all reachable nodes. Look for phrases like “fewest moves,” “minimum number of operations,” or “can you reach.”

Breadth-First Search explores nodes level by level using a queue.

# BFS on graph (adjacency list)
from collections import deque

def bfs(self, graph, start):
    q = deque()
    visited = [False] * len(graph)

    q.append(start)
    visited[start] = True

    while q:
        node = q.popleft()

        # Process node
        print(node, end=" ")

        # Explore neighbors
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                q.append(neighbor)
ID Title Link Solution
841 Keys and Rooms Link Solution

BFS on Grid

When to use: The problem gives you a 2D matrix/grid and asks for shortest distance between cells, number of connected components (islands), or nearest cell of a certain type. Look for “grid,” “matrix,” “4-directional,” or “adjacent cells.”

BFS for 2D grid problems (4-directional or 8-directional).

BFS expands outward on a grid 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 1 2 3 4 5 2 3 # 5 6 3 4 5 6 7 4 5 6 7 8 BFS wavefront expands one step at a time from start Wall at (2,2) forces BFS to go around it Distance from start 0 (start) 1–2 3–4 5–6 7–8 Wall 
from collections import deque

# BFS on 2D grid (4-directional)
def bfsGrid(self, grid, start, target):
    m, n = len(grid), len(grid[0])

    q = deque([start])
    dist = [[-1] * n for _ in range(m)]

    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    dist[start[0]][start[1]] = 0

    while q:
        x, y = q.popleft()

        if (x, y) == target:
            return dist[x][y]

        for dx, dy in dirs:
            nx, ny = x + dx, y + dy

            if (0 <= nx < m and 0 <= ny < n and
                grid[nx][ny] != '#' and dist[nx][ny] == -1):

                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    return -1


# Count connected components (Number of Islands)
def numIslands(self, grid):
    m, n = len(grid), len(grid[0])
    count = 0

    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1

                q = deque([(i, j)])
                grid[i][j] = '0'

                while q:
                    x, y = q.popleft()

                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy

                        if (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1'):
                            grid[nx][ny] = '0'
                            q.append((nx, ny))

    return count
ID Title Link Solution
200 Number of Islands Link Solution
695 Max Area of Island Link Solution

Multi-source BFS

When to use: The problem asks for the distance from ANY source (not one specific source). Classic signals: “distance to nearest 0,” “rotting spreads from all rotten oranges simultaneously,” or “fill from all gates at once.”

Start BFS from multiple sources simultaneously – enqueue all starting points before the loop begins.

Multi-source BFS — distance to nearest source 0 1 2 3 4 0 src 1 2 1 0 src 1 2 3 2 1 2 3 2 3 2 3 2 1 2 3 2 1 0 src 1 2 All sources enqueued at distance 0 BFS expands from every source simultaneously. Each cell shows distance to the nearest source. Legend Source (dist 0) Dist 1 Dist 2 Dist 3 
from collections import deque

# Multi-source BFS (e.g., 01 Matrix)
def updateMatrix(self, mat):
    m, n = len(mat), len(mat[0])

    q = deque()
    dist = [[-1] * n for _ in range(m)]

    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    # Add all zeros as starting points
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                q.append((i, j))
                dist[i][j] = 0

    while q:
        x, y = q.popleft()

        for dx, dy in dirs:
            nx, ny = x + dx, y + dy

            if (0 <= nx < m and 0 <= ny < n and dist[nx][ny] == -1):
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    return dist
ID Title Link Solution
286 Walls and Gates Link Solution
542 01 Matrix Link -
317 Shortest Distance from All Buildings Link Solution
994 Rotting Oranges Link Solution

BFS for Shortest Path

When to use: You need the shortest path and all edges have equal weight (or cost = 1 per step). Look for “minimum number of steps,” “shortest transformation sequence,” or “fewest moves to reach target.”

BFS finds shortest path in unweighted graphs – the first time you reach a node is guaranteed to be via the shortest path.

# Shortest path in unweighted graph
from collections import deque

def shortestPath(self, graph, start, target):
    q = deque()
    dist = [-1] * len(graph)

    q.append(start)
    dist[start] = 0

    while q:
        node = q.popleft()

        if node == target:
            return dist[node]

        for neighbor in graph[node]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[node] + 1
                q.append(neighbor)
ID Title Link Solution
1091 Shortest Path in Binary Matrix Link Solution
127 Word Ladder Link -
433 Minimum Genetic Mutation Link Solution
1197 Minimum Knight Moves Link Solution

Level-order Traversal

When to use: The problem asks you to process a tree level by level. Look for “level order,” “zigzag order,” “vertical order,” “right side view,” or “cousins in a binary tree.”

BFS for tree level-order traversal – use q.size() to process one complete level per iteration.

# Binary Tree Level Order Traversal
from collections import deque

# Binary Tree Level Order Traversal
def levelOrder(self, root):
    result = []
    if not root:
        return result

    q = deque([root])

    while q:
        size = len(q)
        level = []

        for _ in range(size):
            node = q.popleft()
            level.append(node.val)

            if node.left:
                q.append(node.left)

            if node.right:
                q.append(node.right)

        result.append(level)

    return result


# Zigzag Level Order Traversal
def zigzagLevelOrder(self, root):
    result = []
    if not root:
        return result

    q = deque([root])
    leftToRight = True

    while q:
        size = len(q)
        level = [0] * size

        for i in range(size):
            node = q.popleft()

            index = i if leftToRight else (size - 1 - i)
            level[index] = node.val

            if node.left:
                q.append(node.left)

            if node.right:
                q.append(node.right)

        result.append(level)
        leftToRight = not leftToRight

    return result
ID Title Link Solution
102 Binary Tree Level Order Traversal Link Solution
103 Binary Tree Zigzag Level Order Traversal Link Solution
314 Binary Tree Vertical Order Traversal Link Solution
429 N-ary Tree Level Order Traversal Link Solution
993 Cousins in Binary Tree Link Solution
863 All Nodes Distance K in Binary Tree Link Solution

BFS with State

When to use: The shortest path depends on more than just position – you also need to track keys collected, obstacles eliminated, a bitmask of visited nodes, or other extra dimensions. Look for “at most k obstacles,” “collect all keys,” or “visit all nodes.”

BFS when state includes more than just position – expand the visited array to cover all state dimensions.

BFS with state = (position, keys_collected) Grid with keys & doors S · A a · · · b B key (collect) door (need key) State = (row, col, keys_bitmask) Bitmask tracks collected keys: a b = 00 (no keys) ❶ Start: (0, 0) 0 0 no keys ↓ pick up key a ❷ Got key a: (1, 0) 1 0 has a → can open A ↓ pick up key b ❸ Got both: (2, 1) 1 1 has a,b → can open B Same cell can be visited with different key sets → different states! 
# BFS with state (e.g., Shortest Path with Obstacle Elimination)
from collections import deque

def shortestPath(self, grid, k):
    m, n = len(grid), len(grid[0])

    visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]

    q = deque()
    # state: (x, y, obstacles_eliminated, steps)
    q.append((0, 0, 0, 0))

    visited[0][0][0] = True

    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while q:
        x, y, obstacles, steps = q.popleft()

        if x == m - 1 and y == n - 1:
            return steps

        for dx, dy in dirs:
            nx, ny = x + dx, y + dy

            if 0 <= nx < m and 0 <= ny < n:
                newObstacles = obstacles + grid[nx][ny]

                if newObstacles <= k and not visited[nx][ny][newObstacles]:
                    visited[nx][ny][newObstacles] = True
                    q.append((nx, ny, newObstacles, steps + 1))

    return -1
ID Title Link Solution
1293 Shortest Path in a Grid with Obstacles Elimination Link -
847 Shortest Path Visiting All Nodes Link -

Summary: When to Use Each BFS Pattern

Pattern When to Use Time Space
Basic BFS Shortest path (unweighted), level-order O(V+E) O(V)
Grid BFS Grid shortest path, nearest cell O(M × N) O(M × N)
Multi-source Distance from ANY source O(M × N) O(M × N)
Level-order Tree level processing O(N) O(N)
BFS + State Multiple dimensions (keys, masks) O(text{States}) O(text{States})

More templates