Multi-Source BFS
What you'll learn: How to run BFS from multiple starting points simultaneously and why it's powerful for distance problems.
The Core Idea
Instead of starting BFS from a single source vertex, multi-source BFS begins from multiple sources at once. You initialize the queue with all starting points before the traversal begins, treating them as if they're all at "distance 0."
Think of it like dropping multiple stones into a pond simultaneously—the ripples from each stone spread outward at the same rate, naturally finding which points of land each ripple reaches first.
How It Works
The setup is simple but clever:
- Initialize the queue with all source vertices (not just one)
- Mark all sources as visited with distance 0
- Run standard BFS—the algorithm handles the rest automatically
The beauty: vertices get visited in order of their distance to the nearest source, because all sources start expanding simultaneously.
Why This Matters
Multi-source BFS elegantly solves problems like:
- Distance to nearest exit: Given a grid with multiple exits, find each cell's distance to its closest exit
- Rotting oranges: Fresh oranges adjacent to rotten ones rot simultaneously each minute
- 0/1 Matrix: Find each cell's distance to the nearest 0
- Fire spread simulation: Multiple fire sources spreading simultaneously
Instead of running separate BFS from each source and comparing results (slow!), one multi-source BFS finds all nearest-source distances in a single pass.
The Key Insight
By loading all sources into the queue initially, you're essentially treating them as one "super-source" at level 0, letting BFS naturally compute minimum distances.
Key Takeaway: Multi-source BFS initializes the queue with all starting points simultaneously, efficiently solving "distance to nearest source" problems in one traversal instead of many.