05. BFS

TL;DR

Expand a frontier layer-by-layer from a start (or multiple sources) in a graph or tree—processing all distance-(d) nodes before distance-((d+1)). On unweighted graphs this yields shortest path edge-count; on trees it yields level order. Multi-source seeds all queues initially; bidirectional BFS meets in the middle on huge branching factors.

Core Basics

Object: queue-driven layer expansion; shortest path in unweighted graphs, or min steps in implicit state spaces.
State key: visited set must match what defines “seen configuration” (position, mask, cost bucket for 0-1 BFS variant).
Staff-level bar: contrast BFS frontier cost with Dijkstra when weights appear.

Recognition Cues

Phrases: "shortest path", "minimum steps", "level order", "rotting", "word ladder", "nearest gate", "unweighted".
Shapes: grid as implicit graph; adjacency list; tree root given; state graph for string mutations.

Use-case Lens

Best when: every edge/action has equal cost and the first time you reach a node is the shortest path.
Not for: weighted shortest paths; use Dijkstra/0-1 BFS depending on weights.
Main invariant: the queue holds the current frontier in nondecreasing distance order.
Interview move: call out when you mark visited: usually when enqueuing, not when dequeuing, to avoid duplicate work.

Diagram

Loading diagram…

Step-by-step Visual

Example: shortest path from A to F in an unweighted graph.

Loading diagram…

BFS works because the queue processes distance layers in order: distance 0, then all distance 1, then all distance 2, and so on.

Understanding

BFS explores increasing radius: a queue holds the current wavefront; dequeuing processes a node at distance (d); enqueueing neighbors schedules distance (d+1). Visited marks prevent reprocessing—level size snapshot yields clean level lists. Multi-source is equivalent to super-source connected to all starts with zero-cost edges.

Generic Recipe

Initialize queue with start node(s); mark visited with distance 0 (or level 0).
While queue not empty: optionally record levelSize = queue.length for level-order batching.
Dequeue front; for each unvisited neighbor in allowed moves: mark, set distance/parent, enqueue.
For shortest path on grid: directions arrays; bounds check; obstacle check.
Multi-source: enqueue all sources at distance 0 before expanding.
Bidirectional: alternate expanding smaller frontier; stop when frontiers intersect (careful visited bookkeeping).

Complexity

Time: (O(V + E)) for explicit graph; grid (O(\text{rows} \times \text{cols})) with constant neighbor fan-out.
Space: (O(V)) or (O(\min(V, \text{frontier width}))) for queue plus visited set/map.

Memory Hooks

Operational mantra: seed the frontier, visit each state once, and trust level order only for equal-cost edges.
Anti-panic: BFS means "first time reached is shortest" only when all edge costs are equal; otherwise switch models.

Study Pattern (SDE3+)

Recognition drill (10 min): identify level-order, multi-source, implicit-graph, and bidirectional BFS cues.
Implementation sprint (25 min): code a grid BFS with distance and a tree level-order traversal; mark visited on enqueue.
Staff follow-up (10 min): discuss weighted edges, memory pressure from wide frontiers, and queue seeding for multi-source cases.

Generic Code Template

Go

package main

type gridPoint struct {
	row int
	col int
}

// Shortest steps in binary grid: 0 empty, 1 blocked; four-directional.
func shortestPathBinaryGrid(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return -1
	}
	lastRow := len(grid) - 1
	lastCol := len(grid[0]) - 1
	if grid[0][0] == 1 || grid[lastRow][lastCol] == 1 {
		return -1
	}
	directions := []gridPoint{{row: 1, col: 0}, {row: -1, col: 0}, {row: 0, col: 1}, {row: 0, col: -1}}
	queue := []gridPoint{{row: 0, col: 0}}
	grid[0][0] = 1
	distance := 1
	for len(queue) > 0 {
		levelSize := len(queue)
		for step := 0; step < levelSize; step++ {
			current := queue[0]
			queue = queue[1:]
			if current.row == lastRow && current.col == lastCol {
				return distance
			}
			for _, delta := range directions {
				nextRow := current.row + delta.row
				nextCol := current.col + delta.col
				if nextRow < 0 || nextCol < 0 || nextRow > lastRow || nextCol > lastCol {
					continue
				}
				if grid[nextRow][nextCol] != 0 {
					continue
				}
				grid[nextRow][nextCol] = 1
				queue = append(queue, gridPoint{row: nextRow, col: nextCol})
			}
		}
		distance++
	}
	return -1
}

func main() {}

JavaScript

// Level-order traversal of binary tree (nodes { val, left, right }).
function levelOrder(root) {
  const levels = [];
  if (root === null) {
    return levels;
  }
  const queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    for (let count = 0; count < levelSize; count += 1) {
      const node = queue.shift();
      currentLevel.push(node.val);
      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
    levels.push(currentLevel);
  }
  return levels;
}

// Multi-source BFS sketch: distances initialized from several seeds (grid example).
function multiSourceDistances(grid, sources) {
  const rows = grid.length;
  const cols = grid[0].length;
  const distance = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
  const queue = [];
  for (const point of sources) {
    distance[point.row][point.col] = 0;
    queue.push(point);
  }
  const deltas = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  while (queue.length > 0) {
    const current = queue.shift();
    for (const [deltaRow, deltaCol] of deltas) {
      const nextRow = current.row + deltaRow;
      const nextCol = current.col + deltaCol;
      if (nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols) {
        continue;
      }
      if (distance[nextRow][nextCol] <= distance[current.row][current.col] + 1) {
        continue;
      }
      distance[nextRow][nextCol] = distance[current.row][current.col] + 1;
      queue.push({ row: nextRow, col: nextCol });
    }
  }
  return distance;
}

Variants

Shortest path (unweighted) — grids, implicit graphs, word ladder with adjacency built on the fly.
Level-order tree — queue snapshot per depth; right-side view derived from last node per level.
Multi-source BFS — rotting oranges, walls and gates: seed queue with all origins at distance 0.
Bidirectional BFS — word ladder optimization: expand from beginWord and endWord toward meeting frontiers.

Representative Problems

102. Binary Tree Level Order Traversal — classic level-order
994. Rotting Oranges — multi-source grid BFS
286. Walls and Gates — multi-source from gates
127. Word Ladder — shortest path in implicit graph (bidirectional variant)

Anti-patterns

Using BFS for weighted shortest paths without adaptation—Dijkstra or 0-1 BFS as appropriate.
Forgetting to mark visited at enqueue time—duplicate enqueues blow time (especially grids).
Storing massive visited strings for word problems—prefer pruning + hashing discipline or bidirectional search.
Level-order: mixing one queue with unclear level boundaries—snapshot levelSize before inner loop.

On this page