Breadth-First Search

What breadth-first search is

BFS explores a graph in expanding rings: everything at distance 1 from the start, then everything at distance 2, and so on. The machinery is a queue plus a visited set - pop a node, push its unvisited neighbors, repeat. Because nodes are discovered in order of distance, the first time BFS reaches a node is via a shortest path (in edges).

That single property drives almost every interview use: shortest path in an unweighted graph or grid, minimum number of moves or transformations, and anything phrased 'fewest steps to reach X'. Level-order tree traversal is the same algorithm with no visited set needed.

How to recognize it

Signals: 'shortest', 'minimum number of steps/moves/mutations', 'nearest', or 'level by level'. The state space doesn't have to look like a graph - words one letter apart, lock dials one turn apart, or grid cells one move apart are all edges. If every move costs the same, BFS gives the optimal answer; the moment moves have different costs, you need Dijkstra instead.

The contrast to internalize: DFS answers 'does a path exist / enumerate everything', BFS answers 'what is the closest'. Choosing DFS for a shortest-path question is the classic wrong turn, because DFS finds a path, not the shortest one.

The level-by-level template

Most problems need not just visiting order but the distance itself. Snapshot the queue length at the top of each round: exactly that many nodes form the current level, so process them in an inner loop and increment the level counter after. Marking visited at enqueue time (not dequeue time) is what keeps duplicate states out of the queue.

queue = [start]; visited = {start}; level = 0
while queue not empty:
    for i in 1 .. len(queue):        # exactly one level
        node = queue.pop_front()
        if node is target: return level
        for next in neighbors(node):
            if next not in visited:
                visited.add(next)     # mark at enqueue time
                queue.push_back(next)
    level += 1

Multi-source BFS

When the question asks how far everything is from the nearest of several sources - rotting oranges infecting neighbors, distance-to-nearest-zero in a matrix - seed the queue with all sources at level 0 and run the same loop. The flood expands from every source simultaneously, and each cell is first reached by its nearest source. Simulating one source at a time is the O(n^2) trap; multi-source is one pass.

Common pitfalls

Marking visited at dequeue instead of enqueue - the same node enters the queue many times and the complexity quietly explodes.

Using BFS on weighted edges: 'fewest edges' is not 'lowest cost'. Different costs mean Dijkstra (or 0-1 BFS with a deque for weights of 0 and 1).

Forgetting the level-size snapshot and reading len(queue) inside the loop while pushing to it - levels bleed together and the distance is wrong.

Grid BFS: not validating bounds before reading neighbors, or re-allocating the four-direction array in the innermost loop of a hot path.

Tree level-order: no visited set is needed - adding one is harmless but signals you're pattern-matching without understanding why (trees have no cross edges to revisit).

Worked examples

result = []
queue = [root] if root else []
while queue not empty:
    level = []
    for i in 1 .. len(queue):
        node = queue.pop_front()
        level.append(node.val)
        if node.left: queue.push_back(node.left)
        if node.right: queue.push_back(node.right)
    result.append(level)
return result

queue = all rotten cells; fresh = count of fresh; minutes = 0
while queue not empty and fresh > 0:
    for i in 1 .. len(queue):
        (r, c) = queue.pop_front()
        for (nr, nc) in 4-neighbors in bounds:
            if grid[nr][nc] == FRESH:
                grid[nr][nc] = ROTTEN; fresh -= 1
                queue.push_back((nr, nc))
    minutes += 1
return fresh == 0 ? minutes : -1

words = set(wordList); if endWord not in words: return 0
queue = [beginWord]; steps = 1
while queue not empty:
    for i in 1 .. len(queue):
        word = queue.pop_front()
        if word == endWord: return steps
        for each position p, letter c:
            candidate = word with word[p] replaced by c
            if candidate in words:
                words.remove(candidate)   # visited
                queue.push_back(candidate)
    steps += 1
return 0

Check yourself

Try to answer before revealing - retrieving from memory is what makes it stick.

Frequently asked questions