Enqueue ALL source nodes before the BFS loop begins. The infection wavefront then expands from every source simultaneously — as if they all started at time = 0. Each node records the distance to its nearest source. One BFS pass, zero re-runs.
Multiple starting points spread at the same speed simultaneously
Find minimum distance from every node to its nearest source
Tree infection — some nodes infected at t=0, find spread time
Reverse BFS from all targets, find nearest target from any node
Any "all nodes of type X spread outward" scenario in trees or graphs
💡 Key trick: pre-load ALL sources at distance 0. BFS's level-by-level guarantee means every node automatically receives the distance to its closest source — no per-source re-runs needed.
⚡ Complexity
Time
O(V+E)
Space
O(V)
Identical to single-source BFS — each node visited once. If you ran BFS separately from each of k sources, it would cost O(k × V). Multi-source collapses that to O(V) by treating all sources as a virtual super-source.
Live Animation · Multi-Source BFS · LC #994
Problem
Given a 7-node binary tree with two initially infected nodes (sources = {4, 7}), find the minimum time for infection to reach every node. Pre-load all sources at distance 0 — BFS's level-by-level expansion automatically gives each node its distance to the nearest source.
Input: tree = [1,2,3,4,5,6,7], sources = {4,7} · Answer: dist = {4:0,7:0,2:1,3:1,5:2,6:2,1:2} → max = 2 steps
Step 1 / 1
🔴 Init Sources🌊 Spread✅ Done
Binary Tree (undirected) — sources = {4, 7}
Source (d=0)
d=1
d=2
⏱️
0
time steps
🗂️ Queue
nodes spreading right now
empty
Press ▶ Play or Next ▶ to begin
// Pre-load ALL sources before BFS starts
☕ Java Pattern Skeleton Java 8
// Multi-Source BFS — find dist from every node to nearest source
Queue<Integer> queue = new LinkedList<>();
int[] dist = new int[n + 1];
Arrays.fill(dist, -1);
// Step 1: Enqueue ALL sources at distance 0for (int src : sources) {
queue.offer(src);
dist[src] = 0; // source is at distance 0
}
// Step 2: Standard BFS — wavefront from all sources at oncewhile (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (dist[neighbor] == -1) { // not yet reached
dist[neighbor] = dist[node] + 1;
queue.offer(neighbor);
}
}
}
// dist[i] = distance from node i to its nearest source