What is Breadth-First Search?
Breadth-First Search, or BFS, explores the closest unfinished nodes first. It completes one level before moving to the next.
It helps to know what a tree node is and how a FIFO queue works. The short version is: put discovered nodes in a queue so distance 1 is finished before distance 2 begins.
The Core Idea: Expand by Distance
Look at LC 102: Level Order Traversal. The root has value 1, its children are 2 and 3, and the next level contains 4, 5, 6, and 7.
How do we keep that order without manually tracking every depth? We place 1 in a queue. When 1 leaves, its children enter. Because a queue is first in, first out, 2 and 3 leave before any of their children.
It is like customers taking numbered tickets. Anyone who arrived earlier is served before someone who joined the line later.
How the Queue Moves Through Levels
The Rule You Keep True
Every node already removed from the queue is no farther from the start than any node still waiting in the queue. That is why the first visit gives the shortest distance when every edge has equal cost.
The queue can represent different things:
- Tree levels need no visited set because a tree has one route to each child.
- Graph or grid search needs a visited set because several routes may reach the same node.
- Multi-source spread begins with every source already in the queue.
Rotting Oranges is the one that usually trips us up. All rotten oranges must enter the queue at the beginning. Starting from only one source would measure the wrong minute for cells reached by another source sooner.
Picking the Right Shape
From Rule to Code
- Put the starting node, or every starting node, into a queue.
- Mark each starting node visited before processing begins.
- Remove the next node and inspect it.
- Add each unvisited neighbor and record its distance or level.
- Stop when the queue is empty or when the target is first reached.
Each node enters the queue at most once, so BFS finishes in O(V + E) time for a graph and uses O(V) space.
When to use it
- •You need to process a tree or graph one distance level at a time.
- •You need the shortest path in an unweighted graph or grid.
- •The prompt asks for level order, minimum moves, or the nearest matching state.
- •Several starting points must spread outward at the same time.
How to identify it
- •All edges or moves have the same cost.
- •The answer depends on which state is reached first.
- •Nodes at distance `d` must be processed before nodes at distance `d + 1`.
- •A queue naturally holds the next frontier of work.
Key insights
- →A queue processes nodes in the same order they are discovered.
- →The first time BFS reaches a node is through a shortest unweighted path.
- →Mark graph nodes visited when they enter the queue, not when they leave it.
- →A level can be processed by reading the queue size before that level begins.
- →Multi-source BFS starts by placing every source in the queue at distance zero.
Common mistakes
- 01Using BFS without a visited set on a graph that contains cycles.
- 02Marking a node visited too late and adding the same node to the queue many times.
- 03Mixing nodes from two levels because the level size was not captured first.
- 04Using ordinary BFS when edges have different costs.
- 05Returning the number of processed nodes instead of the number of edges or levels requested.