BFS

What is BFS?

BFS (breadth-first search) visits nodes level by level, processing all nodes at distance 1 from the source before any at distance 2, and so on. It uses a queue (FIFO) to enforce this order - enqueue a node's neighbors before processing any of them, and they naturally form the next level.

The key guarantee: the first time BFS reaches a node, it has taken the fewest possible edges. This makes BFS the go-to algorithm for shortest path in unweighted graphs. DFS makes no such guarantee - it might find a path of length 10 before discovering a path of length 2.

Standard template: enqueue the start node and mark it visited; while the queue is not empty, dequeue a node, process it, then enqueue its unvisited neighbors and mark them visited immediately (not on dequeue).

Multi-source BFS: enqueue ALL source nodes simultaneously before the loop begins. The result is the minimum distance from any source to each node. This pattern appears in "rotting oranges," "walls and gates," and "nearest exit" - problems where multiple starting points spread simultaneously and you want the closest-source distance at every cell.

Core operations

Key patterns

Standard BFS (shortest path)

Spread outward from the source one ring at a time, so every node is reached by the fewest edges possible.

When to use - the problem asks for the minimum number of steps, hops, or moves to a target in an unweighted graph or grid. Checking every possible path is exponential; BFS finds the shortest in a single O(V + E) sweep because it reaches each node at its smallest distance first.

How it works - keep a queue and seed it with the source at distance 0. Each step dequeues a node, then enqueues its unvisited neighbors at distance + 1. Mark a node visited the moment you enqueue it, not when you dequeue it - if you wait, several neighbors can each enqueue the same node before it is processed, and the queue can balloon toward O(V^2). The first distance recorded for a node is its shortest-path distance, since any later route to it is longer or equal. Each vertex is enqueued once and each edge examined once, so the whole traversal is O(V + E).

Multi-source BFS

Start the wave from every source at once, so each node's distance is measured to the nearest source.

When to use - several starting points spread at the same time and you want the closest-source distance at every node: rotting oranges, walls and gates, nearest exit. Running a separate BFS from each of S sources and taking the minimum costs O(S * (V + E)); seeding all sources into one queue collapses that to a single O(V + E) pass.

How it works - before the loop, enqueue every source at distance 0 and mark each visited. The combined frontier then expands ring by ring: level 0 holds all sources, level 1 their unvisited neighbors, and so on. Because every node is first reached by the closest source, the distance it is stamped with is its minimum over all sources. As with single-source BFS, mark on enqueue so a node sitting near two sources is not queued twice, and the one shared sweep stays O(V + E).

Canonical examples

Shortest path in a binary grid

Find the shortest path from top-left to bottom-right through 0 cells, moving in 8 directions. BFS processes cells in order of distance from the source, so the first time we reach the bottom-right cell, we have the minimum path length - no additional checking needed.

Rotting oranges (multi-source BFS)

All rotten oranges spread simultaneously each minute. Multi-source BFS enqueues all initially rotten oranges at distance 0; the BFS then computes each fresh orange's minimum time-to-rot. The answer is the maximum distance found, or -1 if any fresh orange is unreachable.

When to reach for BFS

• You need the minimum number of steps, hops, or moves to reach a target - BFS gives shortest path in unweighted graphs.
• The problem involves level-by-level processing of a tree (right side view, level sums, minimum depth).
• You have multiple starting points that should spread simultaneously - multi-source BFS.
• The problem asks for shortest transformation sequence (word ladder, changing one character at a time).
• You need to find the nearest something in a grid (nearest exit, nearest 0, nearest infected cell).
• DFS would explore "too deep" and miss shorter paths - when order-of-discovery matters, use BFS.

Practice problems

• Binary Tree Level Order Traversal - Level-order BFS; the tree variant without needing a visited set.
• Minimum Depth of Binary Tree - BFS stops the instant it reaches the first leaf.
• Rotting Oranges - Multi-source BFS; all sources spread simultaneously.
• Shortest Path in Binary Matrix - Grid BFS with 8-directional movement.
• Word Ladder - BFS on an implicit graph of words differing by one character.