Breadth First Search

Interviewer cue: “shortest path”, “fewest steps”, “minimum number of moves”, or “level by level” almost always means BFS. Breadth-first search explores everything at distance 1 from the start, then everything at distance 2, and so on — so the first time it reaches a target, that’s guaranteed to be the shortest route (as long as every edge has equal weight).

What you’ll learn

The BFS template: a queue plus a visited set, and why both matter.
Level-order traversal on trees, and traversal on graphs given as an adjacency dict.
Using BFS to find the shortest path length in an unweighted graph.
Multi-source BFS: starting the queue with several nodes at once (the trick behind Rotting Oranges).

The pattern

bfs_template.py

from collections import deque
 
 
def bfs(graph, start):
    visited = {start}                 # mark visited the moment a node is ENQUEUED
    queue = deque([start])
    order = []
 
    while queue:
        node = queue.popleft()        # FIFO: process in the order nodes were discovered
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
    return order
 
 
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2, 4],
    4: [3],
}
 
print("BFS order from 0:", bfs(graph, 0))

bfs_template.py

from collections import deque
 
 
def bfs(graph, start):
    visited = {start}                 # mark visited the moment a node is ENQUEUED
    queue = deque([start])
    order = []
 
    while queue:
        node = queue.popleft()        # FIFO: process in the order nodes were discovered
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
    return order
 
 
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2, 4],
    4: [3],
}
 
print("BFS order from 0:", bfs(graph, 0))

How it works: expanding one layer at a time

diagram BFS visit order from node 0 (layer by layer) mermaid

  graph TD
    N0["0 (#1)"] --- N1["1 (#2)"]
    N0 --- N2["2 (#3)"]
    N1 --- N3["3 (#4)"]
    N2 --- N3
    N3 --- N4["4 (#5)"]

Node 00 is layer 0. Nodes 11 and 22 — both one edge away — form layer 1 and get visited next, before BFS ever looks at node 44 (two edges away). That’s the whole guarantee: BFS finishes an entire layer before starting the next one.

sketch BFS frontier expanding outward, ring by ring p5.js

Each tick reveals the next 'ring' of cells at one greater distance -- exactly how BFS explores a graph one full layer before going any farther.

Worked example: shortest path in an unweighted graph

Carry a distancedistance alongside each queued node. The first time you reach the target, its distance is the shortest possible.

bfs_shortest_path.py

from collections import deque
 
 
def shortest_path_length(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])       # (node, distance from start)
 
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == target:
                return dist + 1        # first arrival at target = shortest path
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
 
    return -1   # target unreachable
 
 
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2, 4],
    4: [3],
}
 
print("shortest 0 -> 4:", shortest_path_length(graph, 0, 4))
print("shortest 0 -> 0:", shortest_path_length(graph, 0, 0))

bfs_shortest_path.py

from collections import deque
 
 
def shortest_path_length(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])       # (node, distance from start)
 
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == target:
                return dist + 1        # first arrival at target = shortest path
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
 
    return -1   # target unreachable
 
 
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2, 4],
    4: [3],
}
 
print("shortest 0 -> 4:", shortest_path_length(graph, 0, 4))
print("shortest 0 -> 0:", shortest_path_length(graph, 0, 0))

Worked example: multi-source BFS on a grid

Rotting Oranges seeds the queue with every already-rotten cell at once, then spreads outward — the same BFS loop, just with more than one starting node.

bfs_grid_multi_source.py

from collections import deque
 
 
def minutes_to_rot_all(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
 
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))     # every already-rotten orange starts the frontier
            elif grid[r][c] == 1:
                fresh += 1
 
    minutes = 0
    while queue:
        r, c, minute = queue.popleft()
        minutes = max(minutes, minute)
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2            # rot it -- this doubles as the visited marker
                fresh -= 1
                queue.append((nr, nc, minute + 1))
 
    return minutes if fresh == 0 else -1
 
 
grid = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1],
]
print("minutes until every fresh orange rots:", minutes_to_rot_all(grid))

bfs_grid_multi_source.py

from collections import deque
 
 
def minutes_to_rot_all(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
 
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))     # every already-rotten orange starts the frontier
            elif grid[r][c] == 1:
                fresh += 1
 
    minutes = 0
    while queue:
        r, c, minute = queue.popleft()
        minutes = max(minutes, minute)
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2            # rot it -- this doubles as the visited marker
                fresh -= 1
                queue.append((nr, nc, minute + 1))
 
    return minutes if fresh == 0 else -1
 
 
grid = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1],
]
print("minutes until every fresh orange rots:", minutes_to_rot_all(grid))

Complexity

BFS visits every node and edge at most once: $O(V + E)$ time, and $O(V)$ space for the visitedvisited set plus whatever is sitting in the queue at once (at most one full layer).

When to use it

Shortest path / fewest steps in an unweighted graph (or a grid where every move costs the same).
Level-by-level processing (tree level sums, “print each level”).
Multi-source spreading — infection, fire, rot, or “distance from the nearest X” problems where several starting points exist simultaneously.

If edges have different weights, BFS’s “first arrival = shortest” guarantee breaks — that’s Dijkstra’s territory instead.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 1091 — Shortest Path in Binary Matrix · Medium

Problem. In an n x nn x n binary matrix, return the length of the shortest clear path from the top-left to the bottom-right, moving in 8 directions through 00 cells only. Return -1-1 if no such path exists. Path length counts cells visited.

Constraints. 1 <= n <= 1001 <= n <= 100, cells are 00 or 11.

Examples. [[0,1],[1,0]][[0,1],[1,0]] gives 22 · [[0,0,0],[1,1,0],[1,1,0]][[0,0,0],[1,1,0],[1,1,0]] gives 44 · [[1,0,0],[1,1,0],[1,1,0]][[1,0,0],[1,1,0],[1,1,0]] gives -1-1

Editorial

BFS explores in non-decreasing distance order, so the first time it reaches the target it has found a shortest path. That is the property DFS lacks, and it is why shortest path on an unweighted graph is always BFS.

Time $O(n^2)$ — each cell is enqueued at most once. Space $O(n^2)$ .

Three details:

Eight directions. The nested drdr/dcdc loops over (-1, 0, 1)(-1, 0, 1) produce nine offsets including (0, 0)(0, 0), which is harmless because the current cell is already marked visited.
Blocked endpoints. [[1,0,0],...][[1,0,0],...] has a blocked start, so it must return -1-1 before any search happens.
Mark on enqueue. Marking at dequeue time lets several neighbours enqueue the same cell first, inflating the queue and risking a stale longer distance.

The path length counts cells, not steps, which is why the initial distance is 11 rather than 00. [[0,1],[1,0]][[0,1],[1,0]] returning 22 is the check for that.

Follow-ups: “Why not DFS?” — it does not visit in distance order. “Weighted cells?” — Dijkstra; see Shortest Paths. “A* instead?” — with a distance heuristic it explores less, and is the practical choice on large grids. “Return the path?” — store a parent per cell and walk back.

LC 752 — Open the Lock · Medium

Problem. A lock has four wheels showing '0''0' to '9''9', starting at "0000""0000". Each move turns one wheel one slot. Some states are deadends and may not be visited. Return the minimum moves to reach targettarget, or -1-1.

Constraints. 1 <= len(deadends) <= 5001 <= len(deadends) <= 500, targettarget is four digits and not "0000""0000" unless stated.

Examples. deadends = ["0201","0101","0102","1212","2002"], target = "0202"deadends = ["0201","0101","0102","1212","2002"], target = "0202" gives 66 · deadends = ["8888"], target = "0009"deadends = ["8888"], target = "0009" gives 11 · a fully-surrounded start gives -1-1

Editorial

There is no adjacency list here. The graph is implicit: a state is a string, and its neighbours are generated by a rule. Recognising that a puzzle’s state space is a graph is the transferable skill — the same reframing turns Rubik’s cube, word ladders and sliding puzzles into BFS.

Time $O(10^4 \times 8)$ — bounded by the state space, not the input. Space $O(10^4)$ .

Three guards, each with a test:

"0000""0000" in deadends — return -1-1 immediately; you cannot begin.
target == "0000"target == "0000" — zero moves, and the search would otherwise never check the start.
Wraparound with % 10% 10 — 99 turns up to 00. Python’s modulo also keeps (0 - 1) % 10 == 9(0 - 1) % 10 == 9 correct without a special case.

The third test case surrounds "8888""8888" with all eight of its neighbours as deadends, so it is unreachable — -1-1.

Follow-ups: “Speed it up?” — bidirectional BFS from both the start and the target roughly square-roots the explored space, and is the standard follow-up here. “More wheels?” — the state space grows as $10^w$ ; BFS still works but bidirectional search becomes important. “Weighted turns?” — Dijkstra.

LC 127 — Word Ladder · Hard

Problem. Given beginWordbeginWord, endWordendWord and a wordListwordList, return the number of words in the shortest transformation sequence changing one letter at a time, where every intermediate word must be in wordListwordList. Return 00 if impossible.

Constraints. 1 <= len(beginWord) <= 101 <= len(beginWord) <= 10, 1 <= len(wordList) <= 50001 <= len(wordList) <= 5000, all words the same length, lowercase.

Examples. "hit" -> "cog""hit" -> "cog" with ["hot","dot","dog","lot","log","cog"]["hot","dot","dog","lot","log","cog"] gives 55 · without "cog""cog" gives 00

Editorial

Another implicit graph: words are nodes, and an edge exists between words differing in exactly one letter. BFS then gives the shortest ladder.

Time $O(N \times L \times 26)$ for NN words of length LL. Space $O(N)$ .

The neighbour-generation choice is what makes it fast. Comparing every pair of words is $O(N^2 L)$ — with N = 5000N = 5000 that is 250 million character comparisons. Generating the L × 26L × 26 candidate mutations and testing set membership is $O(L \times 26)$ per word, which at L = 10L = 10 is 260 lookups. That inversion — generate and test rather than compare — is the main lesson.

Removing from wordswords as you enqueue serves as the visited set, which is both shorter and avoids the duplicate-enqueue problem. It does mutate the caller’s set (a copy of the list here), which is worth mentioning.

The early endWord not in wordsendWord not in words check matters: without it the BFS explores the entire reachable space before concluding failure.

Follow-ups: “Return the actual sequence (LC 126)?” — much harder; you must record predecessors and reconstruct all shortest paths. “Speed it up?” — bidirectional BFS from both ends, the standard optimisation. “Precompute buckets?” — group words by wildcard patterns like h*th*t, giving $O(N L)$ preprocessing and cheaper neighbour lookup. “Very long words?” — the L × 26L × 26 generation dominates, so pattern buckets win.

LeetCode problem set

#	Problem	Difficulty	The twist
102	Binary Tree Level Order Traversal	Medium	The tree-BFS template, no `visitedvisited` set needed
994	Rotting Oranges	Medium	Multi-source BFS on a grid, exactly as above
127	Word Ladder	Hard	BFS over an implicit graph where “neighbors” are one-letter-different words
200	Number of Islands	Medium	(BFS variant) — flood-fill each unvisited land cell with a queue instead of recursion
1091	Shortest Path in Binary Matrix	Medium	Grid BFS with 8-directional moves

Recap

BFS = queue + visited set, mark visited the moment you enqueue.
Because it finishes one full layer before starting the next, the first time it reaches a target is guaranteed shortest — but only when every edge/move costs the same.
Multi-source BFS just seeds the queue with several starting nodes instead of one; everything else is identical.
$O(V + E)$ time, $O(V)$ space.

Next: Depth First Search — the go-deep-first counterpart, for connected components, path existence, and cycle detection.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Breadth First Search

What you’ll learn

The pattern

How it works: expanding one layer at a time

Worked example: shortest path in an unweighted graph

Worked example: multi-source BFS on a grid

Complexity

When to use it

Practice — real LeetCode problems

LC 1091 — Shortest Path in Binary Matrix · Medium

LC 752 — Open the Lock · Medium

LC 127 — Word Ladder · Hard

LeetCode problem set

Recap

Was this page helpful?