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).

Example: fewest hops from a source. Given edges 0-1, 0-2, 1-3, 2-3, 3-4 and start 0, dequeuing 0 enqueues neighbors 1 and 2 at distance 1, and 1 then reaches 3 at distance 2 - so when 2 is dequeued next, 3 is already visited and the 2-3 edge adds nothing. The last node, 4, comes off the queue at distance 3, and the visit order reads 0, 1, 2, 3, 4 at distances 0, 1, 1, 2, 3. The visualizer below steps through each dequeue and enqueue.

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).

Example: distance from the nearer of two sources. Seed sources 0 and 4 into the graph 0-1, 1-2, 2-3, 3-4, 0-5, 5-6 at distance 0 and the shared queue spreads both waves at once: 1, 5, and 3 are reached at minute 1, then 2 and 6 at minute 2. Node 2 sits two hops from either source, so whichever frontier dequeues first stamps it, and that is where the two waves meet. The visualizer below steps through the shared queue minute by minute.

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.