BFS on graphs
Why it exists
Problem: Finding the shortest path in an unweighted graph by exhaustively exploring all paths is incredibly slow and can get stuck in infinite loops on cycles.
Better idea: Explore the graph in concentric layers (rings). Check all neighbors at distance 1, then distance 2. This guarantees the first time you reach a node, it's via the shortest path.
Mental model
Concentric ripples in a pond: explore everything 1 hop away before looking at anything 2 hops away.
Use a Queue and a `visited` set. Pop a node, then enqueue all its unvisited neighbors, marking them visited AT ENQUEUE TIME. The visited set is the phase invariant: each node is marked visited at most once, preventing infinite loops on any cycle.
Repeated decision: Which node comes off the front of the queue next, and which of its unvisited neighbours get enqueued?
Explanation
Breadth-First Search (BFS) is the canonical algorithm for exploring unweighted graphs and determining the absolute shortest path in terms of edge count. It relies on a First-In-First-Out (FIFO) queue to ensure nodes are processed strictly in order of their radial distance from the origin.
To avoid infinite loops in cyclic graphs, a `visited` set is critical. The central invariant of this phase is: each node is marked visited at most once.
A classic bug is marking nodes as visited when they are dequeued. You must mark them visited at ENQUEUE time. If you wait until dequeue, a node might be reached and enqueued multiple times by different paths in the same layer, leading to redundant work and a blown-up queue.
Here is a hand-trace on a small undirected graph: `A-B`, `A-C`, `B-D`.
1. Start `A`. Enqueue `A`, mark `A` visited. Queue: `[A]`.
2. Pop `A`. Neighbors are `B`, `C`.
3. Enqueue `B`, mark `B`. Enqueue `C`, mark `C`. Queue: `[B, C]`.
4. Pop `B`. Neighbor `A` is visited. Neighbor `D` is unvisited: enqueue `D`, mark `D`. Queue: `[C, D]`.
5. Pop `C`. Neighbor `A` is visited. Queue: `[D]`.
6. Pop `D`. Neighbor `B` is visited. Queue: `[]`. Done.
Whether the graph is directed or undirected, BFS works the exact same way. Just ensure you are using the correct adjacency list for the directedness of the graph. The guarantee is firm: BFS finds the shortest path in number of edges, and only on unweighted graphs.
Key points
- The Guarantee: BFS finds the shortest path in number of edges, and only on unweighted graphs.
- Mark visited on ENQUEUE: Always mark a node as visited before pushing it to the queue. This prevents the same node from being enqueued multiple times.
- Complexity: O(V+E) time, O(V) space. Each vertex is enqueued at most once, and each edge is checked at most twice.
Common mistakes
- Marking visited at dequeue time: Dequeue-time marking lets a node be enqueued many times before it's ever processed, leading to exponential queue growth and massive duplicated work on dense graphs.
Recall questions
- What data structure does BFS use to maintain its exploration order?
- When should a node be marked as visited in BFS?
- What shortest-path guarantee does BFS make, and under what condition?
Questions & answers
Find the minimum number of hops to reach a target node in a social network.
Use standard BFS from the source node, tracking the distance level. The first time the target is reached, that is the minimum hops.
Approach: Recognize that hops means an unweighted graph, making BFS the perfect fit.
Find the shortest path out of a 2D maze.
Model the maze cells as graph nodes and adjacent open cells as unweighted edges. Run BFS from the start to find the nearest exit.
Approach: 2D grids are implicit unweighted graphs where BFS finds the shortest path.
Continue learning
Previous: Graph representations
Next: When BFS Stops Working
Next: Connected Components