Breadth-First Search (BFS)
Breadth-first search (BFS) traverses a graph layer by layer using a queue. It finds shortest paths in unweighted graphs.
START
Queue (FIFO)
Visit order
Nothing visited yet
Start at A. Mark it discovered and enqueue it.
Next
Dequeue A. It is now visited — position 1 in the order.
Start
Edges
Intuition
Imagine dropping a stone in a calm pond.
Ripples generated by the stone move outward in concentric circles.
BFS works similarly: starting from a source node, it visits all immediate neighbors (first ripple), then neighbors of neighbors (second ripple), and so on.
Concept
Breadth-First Search (BFS) explores a graph in rings around the start node: every node one edge away, then every node two edges away, finishing each distance before starting the next.
It uses a Queue (First-In-First-Out) data structure to keep track of nodes to explore.
How it Works
- Enqueue the starting node and mark it as visited.
- While the Queue is not empty:
- Dequeue a node (let's call it current).
- Visit current.
- Enqueue all unvisited neighbors of current and mark them as visited.
Step-by-Step Breakdown
Watch the visualization above:
- Solid blue node: The node just dequeued and being processed.
- Pale blue node with a blue outline: Discovered and waiting in the queue.
- Green node: Already dequeued (visited).
- Queue (FIFO) panel: The waiting nodes, front first. The front is dequeued next.
Trace: BFS from A on the seven-node tree
start A
A goes into the queue and into visited together — the code marks a node when it is discovered, not when it is dequeued, so nothing can be queued twice. A is 0 edges from the start.
queue [A]
shift A
Neighbours B and C are unvisited: mark both and push them. Both are 1 edge from A.
[B, C]
shift B
Neighbours A, D, E. A is already in visited, so the check skips it. D and E are marked and pushed at distance 2.
[C, D, E]
shift C
C was queued before D and E, so it leaves before them — every distance-1 node is dequeued before any distance-2 node. F and G are pushed at distance 2.
[D, E, F, G]
shift D…G
Each leaf's only neighbour is its parent, already visited. Nothing is pushed, the queue drains, and the loop ends.
[ ]
the levels
Visit order A | B C | D E F G. The queue only ever held nodes of two adjacent distances, oldest first, so no node is dequeued before a node nearer the start. The first time BFS reaches a node is therefore along a fewest-edges path — the property DFS does not have.
0 | 1 | 2
the count
Seven dequeues, and each of the six edges is checked once from each end: 12 neighbour checks. Nodes plus twice the edges is the O(V + E).
7 + 12
When to Use
Use BFS when:
- Finding the shortest path in an unweighted graph (e.g., fewest hops to reach a destination).
- Finding all nodes within a certain distance from a source (e.g., friends of friends).
- Level-order traversal of a tree.
When NOT to Use
- Memory Constraints: BFS stores all nodes at the current level, which can be memory-intensive for wide graphs.
- Weighted Graphs: For shortest paths in weighted graphs, use Dijkstra's Algorithm instead.
How to Identify
Problems asking for "shortest path", "least number of steps", or "nearest neighbor" usually imply BFS.
Preparing for interviews? This topic is also taught as a pattern:
Introduction to BFS
Applying for software engineering roles? Free, no sign-up: