Breadth-First Search starts at a source node and explores every neighbor at distance 1 before visiting any neighbor at distance 2, then distance 3, and so on — always processing the closest unvisited nodes first. The core mechanism is a FIFO queue: dequeue a node, process it, enqueue all its unvisited neighbors. Because the queue enforces first-in-first-out order, every node is reached by the path with the fewest edges — making BFS the natural algorithm for shortest-path problems in unweighted graphs. BFS runs in O(V + E) time and O(V) space for the queue and visited set — it visits every vertex at most once and examines every edge at most once (twice for undirected). The algorithm terminates naturally when the queue is empty, meaning all reachable nodes have been explored. BFS extends from single graphs to 2D grids (where each cell is a vertex with edges to 4 or 8 neighbors), to multi-source problems (where multiple starting nodes are enqueued simultaneously), and to implicit state-space graphs (where configurations are vertices and transitions are edges).

BFS finds the shortest path (minimum number of edges) in an unweighted graph because of FIFO ordering: a node at distance d is always dequeued and processed before any node at distance d+1. The first time BFS reaches a node, no shorter path exists — if there were a shorter path, that node would have been enqueued (and dequeued) earlier. This guarantee does NOT hold for weighted graphs — if edges have different costs, Dijkstra's algorithm is needed. For unweighted graphs, BFS is both optimal and O(V+E) — no algorithm can do better.

Standard BFS starts from a single source. Multi-source BFS starts from ALL given sources simultaneously — enqueue every source node at level 0, then expand outward level by level. The result: each non-source node is assigned the distance to its nearest source in O(V+E) total. Without multi-source BFS, you would run single-source BFS from each source separately — O(S × (V+E)) where S is the number of sources. Multi-source BFS is the key to solving "Rotting Oranges" (LC 994), "01 Matrix" (LC 542), "Walls and Gates" (LC 286), and any problem asking "distance to nearest X."

A 2D grid is an implicit graph where each cell is a vertex and edges connect to 4-directional (or 8-directional) neighbors. You never build an adjacency list — instead, use a directions array int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}} and iterate. Grid BFS is the dominant pattern in LeetCode graph problems — "Number of Islands," "Shortest Path in Binary Matrix," "01 Matrix," and "Walls and Gates" all use it. The main trap is bounds checking: always verify 0 <= nr < rows && 0 <= nc < cols before accessing the grid.

BFS and DFS both traverse all reachable vertices in O(V+E), but they answer different questions. BFS finds the shortest path (minimum edges) and processes nodes level by level — use it when the problem asks for "minimum steps," "nearest," or "shortest." DFS explores depth-first and backtracks — use it when the problem asks for "all paths," "connected components," "cycle detection," or "topological sort." The wrong choice doesn't just give a suboptimal solution — it gives the wrong answer entirely. Using DFS for "minimum steps" yields a valid path but not the shortest one.

Build this from scratch once — it makes the mechanics concrete. In practice, BFS is boilerplate: queue + visited + neighbor loop. Memorise the template.

BFS interview problems fall into three patterns: single-source shortest path ("minimum number of steps to reach target"), multi-source expansion ("how long until all cells are affected"), and implicit graph BFS ("state-space search where nodes are configurations"). Recognise the BFS signal: any problem asking for "minimum," "shortest," "nearest," or "fewest moves" in an unweighted context is almost certainly BFS.

→ See the full BFS practice set