BFS explores a graph like ripples on still water — a wavefront that visits all neighbors of the start, then all their neighbors, and so on.
Imagine dropping a stone: ripples expand outward in perfect circles, touching everything at distance 1 before distance 2.
The data structure behind this ripple is a FIFO queue: the first node found is the first node processed, so nothing jumps ahead of its own “generation.”
How It Works
- Initialize: mark the starting node visited and enqueue it.
- Process: dequeue the front node — that’s the current node.
- Explore: examine every neighbor; mark unvisited neighbors visited and enqueue them.
- Repeat: continue until the queue is empty. Every reachable node has been visited in BFS (level) order.
Key Insight
Because the queue processes nodes in the order they were discovered, BFS visits every node at distance k before any node at distance k+1. That makes the first time BFS reaches a node the shortest path in edges to it — no other algorithm finds fewest-edge paths in an unweighted graph with less work.
The visited set guarantees each node is enqueued exactly once, keeping the whole traversal linear in V + E.
Worked Example
Run BFS on the visualizer’s default undirected graph (start A):
- Queue
[A]; visited{A}. - Dequeue A → neighbors B, C unvisited → queue
[B, C]. - Dequeue B → neighbors D, E unvisited → queue
[C, D, E]. - Dequeue C → neighbor F unvisited (E already enqueued) → queue
[D, E, F]. - Dequeue D, E, F → no new unvisited neighbors.
BFS order: A → B, C → D, E, F. Every node sits at its true edge-distance from A — that’s the level-by-level guarantee you can watch in the animation as the queue snapshot fills.
Edge Cases & Pitfalls
- Disconnected graphs — BFS only reaches the start’s component. To visit everything, restart from every unvisited node; that loop is how you count connected components.
- Back edges / cycles — the visited set prevents infinite loops; without it, BFS never terminates on cyclic graphs.
- Large graphs — the queue grows to
O(V): the memory cost on very wide graphs. - Weighted graphs — BFS “shortest” means fewest edges. With weighted edges it gives wrong answers — use Dijkstra instead.
Comparison: BFS vs DFS
| Aspect | BFS | DFS |
|---|---|---|
| Data structure | FIFO queue | LIFO stack / recursion |
| Shortest path (unweighted) | Yes | No |
| Memory on wide graphs | High (queue) | Low (path only) |
| Applications | Shortest paths, levels | Topo sort, cycles, SCCs |
Applications
- Shortest path in unweighted graphs (GPS, social-network degrees of separation)
- Web crawling — level-by-level link discovery
- Network broadcasting — flooding messages through a network
- Garbage collection — mark-and-sweep
- Connected components in undirected graphs
Practice Trajectory
- Hand-trace BFS on the visualizer graph starting at B, writing the queue after each dequeue.
- Prove that the first time BFS reaches a node, the path is fewest-edges.
- Explain how a visited set prevents infinite loops on cyclic graphs.
- Modify BFS to count connected components in a disconnected graph.
- Show why BFS gives wrong “shortest paths” on a weighted graph.