Breadth-First Search

What BFS Actually Does

Without BFS, finding the shortest path in an unweighted graph requires trying every possible path from source to target and comparing their lengths. That approach explores paths in arbitrary order. A short path might be discovered late because the search followed a long detour first. The total work grows combinatorially with the number of edges.

BFS avoids this by expanding in distance order. It processes all nodes at distance 1 from the source before any node at distance 2, all distance-2 nodes before any distance-3 node, and so on. The moment the target is reached, no shorter path can exist because every shorter path would have been discovered in an earlier wave.

The structure has three parts: a visited set that tracks which nodes have entered the queue, the queue itself initialized with the source, and a loop that dequeues a node and enqueues its unvisited neighbors.

What the Queue Represents

The queue in BFS is not just a data structure choice. It represents the frontier: the set of nodes that have been discovered but not yet processed. A stack would produce DFS because it processes the most recently discovered node first. A queue processes the earliest discovered node first, which is always at a smaller or equal distance from the source.

FIFO order creates a natural barrier between distance levels. When the start node is processed, all its neighbors (distance 1) enter the queue. When a distance-1 node is processed and discovers distance-2 neighbors, those neighbors enter the back of the queue, behind all remaining distance-1 nodes. No distance-2 node is processed until every distance-1 node is dequeued. The queue enforces this ordering automatically.

The Visited Set

The visited set tracks which nodes have already entered the queue. Its purpose is to prevent the same node from entering the queue more than once. The timing of when a node is marked visited determines whether this guarantee holds.

Visited marking timing looks trivial but produces subtle correctness failures. In a graph where both A and C connect to B:

The wrong approach: when processing A, B is not yet visited, so B gets added. When processing C, B is still not visited (it's in the queue but not marked), so B gets added again. The queue now has B twice, causing redundant work or incorrect results. In dense graphs, this compounds: if k neighbors all connect to the same node, that node enters the queue k times. Across the entire graph, total queue insertions become O(E) instead of O(V), turning what should be an O(V+E) traversal into O(E^2) in the worst case.

The correct approach: mark B as visited the moment it enters the queue. When C tries to add B, the check fails because B is already marked. Each node enters the queue exactly once.

First Walkthrough

Consider a graph where A connects to B and C, B connects to D, and C connects to D and E. Starting BFS from A:

Notice the key moment at Step 4. Both B and C connect to D, but D was already marked visited when B added it in Step 3. Without visited-on-enqueue, C would add D to the queue a second time, and D would be processed twice. With visited-on-enqueue, D enters the queue exactly once, and the first path to reach it (through B) is the one that determines its distance.

Also notice the FIFO ordering. C entered the queue before D, so C is processed before D even though both are in the queue simultaneously. All distance-1 nodes (B and C) are processed before any distance-2 node (D and E). The queue enforces this without any explicit level tracking.

Tree BFS (Level Order)

BFS applies to three main structures: trees, graphs, and grids. The core loop is the same. The differences are in how neighbors are discovered and whether a visited set is needed.

Trees are acyclic: there is exactly one path from root to any node. This means no visited set is needed. Each node is reached exactly once through its parent.

Graph BFS

Graphs can have cycles and multiple paths to the same node. A visited set is mandatory to prevent infinite loops and duplicate processing.

Grid BFS

Grids are graphs where neighbors are implicit (up/down/left/right). The visited set can be a 2D boolean array or a set of coordinate tuples.

Note the bounds checking: 0 <= nr < rows ensures coordinates are valid before accessing the grid. This replaces the adjacency list lookup in graph BFS.

Tracking Distance

Many BFS problems require knowing not just which nodes you visited, but when you visited them relative to your starting point. The key question that determines your approach: do you need to know when you cross level boundaries, or just the final distance to specific nodes?

If the problem asks "return nodes grouped by level" or "find the rightmost node at each level," you need explicit boundaries. If it asks "what is the shortest distance to node X," you only need the final number. Both run in O(V+E), but mismatching the approach to the problem adds unnecessary complexity.

Batch Processing (Level by Level)

At the start of each iteration, every node currently in the queue belongs to the same level. If you capture len(queue) before processing anything, that number tells you exactly how many nodes to pop before incrementing your level counter.

Why does this work? You pop a node, then add its children to the queue. Those children belong to the next level, not the current one. But they sit at the back of the queue. The nodes already in the queue when you started are still at the front. By processing exactly the original count, you exhaust all current-level nodes before touching any next-level ones.

Use this approach when you see phrases like "return nodes level by level," "zigzag traversal," "rightmost node at each level," or "average value per level." These all require grouping nodes by depth, not just knowing an individual node's depth.

Storing Distance with Node

Instead of tracking level boundaries globally, you can attach the distance to each node as you enqueue it. When you pop a node, you immediately know how far it is from the start. Use this when you need the distance to a specific target and can exit early once you find it.

Start by enqueueing (start, 0). When you pop (node, dist), check if it is your target. If yes, return dist immediately. If not, enqueue each neighbor as (neighbor, dist + 1).

Use this approach when you see phrases like "minimum number of moves," "shortest path to X," or "fewest steps to reach the goal." You do not need to process entire levels; you just need to know the moment you reach the target. The early exit means you avoid processing nodes you do not care about.

Why BFS Finds Shortest Paths

BFS processes all nodes at distance d before any node at distance d+1. This means distances are finalized in order. When a node at distance d is dequeued, every node at distance d-1 has already been processed and all edges from those nodes have already been examined. Any path to the current node using fewer than d edges would have been discovered during an earlier wave. Since it was not, d is the minimum number of edges from the source.

This guarantee depends on equal-cost edges. When every edge costs 1, distance equals edge count, and FIFO order ensures monotonically increasing distances. A shorter alternative path cannot appear later in the queue because it would have been discovered at a smaller distance, which was already fully processed.

Contrast with DFS: DFS might reach a node via a long detour before finding the short path. DFS explores one branch to completion before considering alternatives. It does not process nodes in distance order, so it cannot guarantee that the first path found is the shortest.

When BFS Breaks

BFS finds shortest paths only when all edges have equal cost. When that assumption does not hold, or when the problem structure does not match distance-ordered exploration, BFS either gives wrong answers or wastes resources.

Weighted graphs. When edges have different costs, the path with the fewest edges can be the most expensive. BFS would return a 1-edge path with cost 100 over a 2-edge path with cost 2 because BFS processes by hop count, not by total weight. For weighted shortest paths, use Dijkstra's algorithm with a priority queue ordered by cumulative cost.

"Find all paths" problems: BFS explores outward but does not naturally track which specific path led to each node. DFS with backtracking explicitly builds and unbuilds paths, making it natural for enumeration.

Wide graphs and memory: BFS stores the entire frontier (current level) in the queue. In a graph where the root has a million children, the queue immediately holds a million nodes. DFS uses O(height) stack space regardless of width, making it more memory-efficient for wide, shallow graphs.

Multi-Source BFS

Some problems ask for the minimum distance from any of several sources to all other nodes. Running BFS from each source separately is O(S x (V + E)) for S sources. Multi-source BFS does it in O(V + E).

Classic example: Rotting Oranges. All rotten oranges start in the queue at time 0. Each minute, rot spreads to adjacent fresh oranges. The answer is the maximum time when the last fresh orange rots (or -1 if some remain).

State-Space BFS

Most BFS problems provide an explicit graph: nodes connected by edges, or a grid with cells. In state-space BFS, the graph is implicit: each configuration is a node, each valid transformation is an edge. BFS explores this implicit graph to find the minimum number of transformations from start to goal.

How to recognize state-space BFS: The problem asks for minimum steps/moves/transformations between configurations. There is no pre-built graph. The approach requires defining what a "state" is and what "moves" connect states. If every move has equal cost (one step), BFS finds the optimal solution.

Common state-space problems:

• Word Ladder: State = current word. Edge = single-letter change to another valid word. The dictionary defines which edges exist.
• Open the Lock: State = 4-digit code like "0000". Each digit can increment or decrement (wrapping 9 to 0 and 0 to 9). Eight possible moves per state. Deadends are "walls" that block certain states.
• Sliding Puzzle: State = board configuration as a string. Edge = swapping the blank tile with an adjacent tile. Goal is the solved configuration.

State Encoding

States must be hashable to use in a visited set. Lists and 2D arrays are mutable and cannot be hashed.

Bidirectional BFS

Standard BFS explores O(b^d) nodes where b is the branching factor and d is the depth. Bidirectional BFS searches from both ends, meeting in the middle, for O(b^(d/2)).

Problem Deep-Dives

The patterns above are tools. The problems below show you how to pick the right tool for the job. Each walkthrough explains why the problem maps to a specific BFS variant, traces through a concrete example, and highlights the decision that makes or breaks the solution.

Rotting Oranges: Multi-Source Spread

Problem. Given an m x n grid where 0 is empty, 1 is a fresh orange, and 2 is rotten, every minute each rotten orange infects its 4-directional neighbors. Return the minimum minutes until no fresh orange remains, or -1 if impossible.

This is multi-source BFS. All rotten oranges begin spreading at the same time, not one after another. That simultaneity is the entire problem. If you BFS from each rotten orange separately, you overcount because the waves from different sources interfere with each other. The fix is to place every rotten orange into the queue at time 0 before the loop starts. They form a single wavefront that expands in lockstep.

The algorithm has three phases. First, scan the grid: count fresh oranges and collect all rotten positions into the queue. Second, run BFS level by level, where each level represents one minute. When a rotten cell infects a fresh neighbor, mark the neighbor as rotten and decrement the fresh count. Third, check whether the fresh count is zero. If yes, return the number of minutes (levels processed). If no, some orange is unreachable from all rotten sources, so return -1.

Each BFS level is one minute because every cell in the queue at time t infects its neighbors at time t+1. FIFO order guarantees that all time-t cells finish before any time-(t+1) cell is processed. This is the same level-boundary technique used in tree BFS, applied to a grid.

Notice the grid itself serves as the visited set. When a fresh orange becomes rotten, we set it to 2 immediately. No separate visited structure is needed because the grid values already encode the three possible states. This is a common grid BFS optimization: mutate the input to avoid allocating a visited array. If the input must stay clean, copy it first.

Complexity: O(m*n) time because each cell is enqueued at most once. O(m*n) space for the queue in the worst case (all cells are rotten).

01 Matrix: Reverse the Question

Problem. Given an m x n binary matrix, return the distance of each cell to the nearest 0.

The naive approach runs BFS from every 1-cell to find its nearest 0, giving O(m²n²) total work because each of the mn cells might trigger its own full-grid BFS. The key insight is to reverse the question: instead of asking "how far is each 1 from a 0," ask "how far does each 0 reach?" The distance from cell A to the nearest 0 equals the distance from the nearest 0 to cell A. Start BFS from all 0-cells simultaneously. This is the same multi-source BFS used in Rotting Oranges, applied to distances instead of time.

Initialize the distance matrix with 0 for every 0-cell and infinity for every 1-cell. Add all 0-cells to the queue. BFS expands outward: when a cell at distance d touches a neighbor still at infinity, that neighbor's distance becomes d+1 and it enters the queue. Because BFS processes cells in order of increasing distance, the first time a cell is reached is guaranteed to be via the shortest path.

The visited check here is implicit: a cell only enters the queue when its distance decreases. Since BFS processes distances in order, each cell's distance is set exactly once (from infinity to its true value). No separate visited set is needed.

Complexity: O(m*n) time and space. Every cell is enqueued once. The algorithm is structurally identical to Rotting Oranges with different source initialization.

Shortest Path in Binary Matrix: 8-Directional BFS

Problem. Given an n x n binary grid where 0 is open and 1 is blocked, find the length of the shortest clear path from top-left to bottom-right. You can move in all 8 directions (including diagonals). The path length includes both the start and end cells.

DFS finds a path but not the shortest one. Consider a 5x5 grid where DFS dives diagonally and gets stuck in a dead end. It backtracks and finds a different route, but that route is 9 cells long. BFS, expanding one ring at a time, would have found the 5-cell path on its first wave through. The reason is structural: DFS commits early and explores deeply before considering alternatives, while BFS explores all paths of length k before any path of length k+1.

The 8-directional movement is the only difference from standard grid BFS. Instead of 4 directions, use all 8 combinations of (dr, dc) where both dr and dc range over {-1, 0, 1}, excluding (0, 0). The path length counts cells, not edges, so the start cell has length 1 and each step adds 1.

Mark visited on enqueue, not dequeue. This distinction matters more here than in most grid problems because 8-directional movement creates more overlapping paths. A cell can be reached from up to 8 neighbors. If you mark visited only when dequeuing, the same cell enters the queue up to 8 times. Mark visited the moment a cell enters the queue, and each cell is processed exactly once.

Complexity: O(n^2) time and space. Each cell is enqueued at most once.

Word Ladder: Implicit Graph

Problem. Given a begin word, an end word, and a dictionary of valid words, find the length of the shortest transformation sequence from begin to end. Each step changes exactly one letter, and every intermediate word must exist in the dictionary.

This is BFS on an implicit graph. Every word is a node. Two words share an edge if they differ by exactly one letter and both appear in the dictionary. The graph is never built explicitly. Instead, BFS discovers neighbors on the fly by trying all possible single-letter substitutions at each position.

There are two strategies for finding neighbors. The brute-force approach compares every word in the dictionary against the current word, checking if they differ by one letter. For N words of length M, this costs O(N*M) per expansion. The wildcard approach replaces each position with a wildcard and looks up a precomputed map. For "hot," the wildcards are "*ot," "h*t," and "ho*." Each maps to a list of matching words. Building the map costs O(N*M), but each lookup is O(1). For large dictionaries, the wildcard approach dominates.

BFS guarantees the shortest chain because every edge costs 1. The first time BFS reaches the end word, no shorter path exists. Any alternative path would have been discovered at an earlier or equal BFS level.

Complexity: O(M^2 * N) where M is word length and N is dictionary size. Building the wildcard map costs O(M * N). Each BFS expansion generates M patterns, each is a string operation costing O(M), across N possible expansions.

Shortest Path with Obstacles: 3D State

Problem. Given an m x n grid with obstacles and an integer k, find the shortest path from (0,0) to (m-1, n-1). You may eliminate at most k obstacles along the way.

Standard grid BFS tracks (row, col) as the state. That breaks here because two paths reaching the same cell with different remaining elimination budgets are fundamentally different. A path with k=3 remaining can punch through obstacles that a path with k=0 cannot. Collapsing them into one visited entry discards potentially winning states.

The fix is to expand the state to (row, col, remaining_k). The visited set becomes three-dimensional. Two entries at the same cell are distinct if they arrived with different elimination budgets. BFS explores all states in order of increasing distance, so the first state to reach the goal is the shortest path regardless of how many eliminations it used.

Consider a concrete example. Path A reaches cell (2,3) with distance 5 and k=2 remaining. Path B reaches the same cell with distance 4 and k=0 remaining. Path B is shorter, but Path A can still eliminate 2 obstacles on its way to the goal. If the only route from (2,3) to the goal passes through an obstacle, Path A wins despite being longer so far. Both states must be kept.

The early exit optimization is worth knowing. If k is at least (rows + cols - 2), you have enough budget to eliminate every obstacle on the Manhattan-distance path from corner to corner. No BFS needed; the answer is rows + cols - 2.

Complexity: O(m * n * k) time and space. Each (row, col, remaining_k) triple is visited at most once. The state space has m * n * (k+1) entries.

BFS vs DFS

Both BFS and DFS explore all reachable nodes. The difference is order: DFS goes deep first (follow one path to its end, then backtrack), while BFS goes wide first (explore all neighbors before going deeper).

Debugging BFS

When BFS produces wrong answers or runs too slowly, check these five areas.

Time and Space Complexity

For grids of size R x C: V = R x C nodes, E = O(R x C) edges (each cell has at most 4 neighbors). So grid BFS is O(R x C).

Practice Problems

BFS problems cluster into recognizable categories: seeing Rotting Oranges as multi-source BFS, Open the Lock as state-space BFS.

Tree BFS

Grid BFS

Multi-Source BFS

State-Space BFS

Reference Templates

Use when the problem asks for level order, per-level aggregation, or depth-by-depth traversal.

Use when edges are unweighted and the goal is shortest path or reachability.

Use when cells are nodes and movement directions define edges.

Use when distance should be measured from the nearest of many starting points.

Use when the graph is implicit and each configuration is a node.

Use when both start and target are known and the search space branches heavily.

Pattern Recap

Tree BFS does not need a visited set because trees are acyclic. Level boundaries are tracked by capturing queue length before processing each level. Use this for level-order traversal, zigzag ordering, and per-level aggregation.

Graph BFS requires a visited set to prevent cycles and duplicate processing. Mark visited on enqueue, not dequeue. The first time any node is reached is via the shortest path in an unweighted graph.

Grid BFS treats cells as nodes and directional offsets as edges. Bounds checking replaces adjacency list lookup. The visited set can be a separate structure or the grid itself when mutation is acceptable.

Multi-Source BFS initializes the queue with all sources at distance 0. One BFS pass finds the nearest source to every node in O(V+E), compared to O(S * (V+E)) for running S separate BFS traversals.

State-Space BFS works on implicit graphs where each configuration is a node and each valid transformation is an edge. States must be hashable for the visited set. When a resource depletes along the path, the state must include that resource as an extra dimension.

Bidirectional BFS searches from both start and target, meeting in the middle. It reduces the search space from O(b^d) to O(b^(d/2)) but requires knowing the target state. It does not work for problems where the target is not a single known configuration.

Rebuilding the Pattern

When BFS feels unclear, start with the problem shape. If the problem asks for minimum steps, minimum distance, or the nearest of something in a structure where all transitions have equal cost, BFS is likely correct. The equal-cost property is what makes FIFO order produce distances in the right sequence. If transition costs differ, the same logic applies but requires a priority queue instead of a plain queue.

After confirming the problem shape, define the state. In explicit graphs, the state is a node ID. In grids, it is a coordinate pair. In state-space problems, it is the full configuration: a word, a lock combination, a board layout. When a resource depletes along the path, such as obstacle eliminations or collected keys, the state must include that resource. Two paths reaching the same position with different resource counts are different states and must be tracked separately.

Then build the loop. Initialize the queue with the starting state at distance 0. Mark it visited immediately. For each dequeued state, generate its neighbors. For each unvisited neighbor, mark it visited and enqueue it with distance incremented by one. The visited check and the visited mark both happen before the enqueue, not after the dequeue. This single timing decision prevents duplicate queue entries and preserves correctness.

Choose the right distance-tracking approach. If the problem needs level boundaries (group by depth, zigzag, per-level stats), capture queue length at the start of each level and process exactly that many nodes. If it only needs the distance to a specific target, store (state, distance) tuples in the queue and exit the moment the target is found.

Finally, check whether the problem has multiple starting points. If it asks for the distance from the nearest of several sources to every other node, initialize all sources in the queue at distance 0 instead of running separate BFS passes. This turns an O(S * (V+E)) approach into a single O(V+E) pass.

Check Your Understanding

Use these questions to check whether you can reason through the pattern without looking at the template.