Pattern Guide
Multi-Source BFS & 0-1 BFS
"BFS from multiple sources simultaneously. 0-1 BFS with deque for mixed weights."
Multi-source BFS starts from all sources simultaneously — equivalent to adding a virtual super-source node connected to all real sources. Finds minimum distance from any source to every node in O(V+E). 0-1 BFS handles graphs with edge weights 0 or 1: use a deque instead of a queue — push to front for weight-0 edges, push to back for weight-1 edges. O(V+E) instead of Dijkstra's O(E log V).
Problems you can solve with this pattern
3 problems · click any to start solving
// Multi-source BFS: find distance from nearest source to every cell
function multiSourceBFS(grid, sources) {
const m = grid.length, n = grid[0].length;
const dist = Array.from({length: m}, () => new Array(n).fill(Infinity));
const queue = [];
// Initialize all sources with distance 0
for (const [r, c] of sources) { dist[r][c] = 0; queue.push([r, c]); }
const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
while (queue.length) {
const [r, c] = queue.shift();
for (const [dr, dc] of dirs) {
const [nr, nc] = [r+dr, c+dc];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] === Infinity) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
return dist;
}
// 0-1 BFS: edge weights are 0 or 1, use deque
function zerOneeBFS(n, edges, src) {
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
const deque = [src]; // front = minimum dist
while (deque.length) {
const u = deque.shift();
for (const [v, w] of (edges[u] || [])) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w === 0) deque.unshift(v); // same dist, push to front
else deque.push(v); // dist+1, push to back
}
}
}
return dist;
}Multi-source BFS: enqueue all sources with distance 0 at start. Process as normal BFS — each node gets minimum distance from any source. Applications: distance to nearest X (nearest exit, nearest gate), spreading fire/rot. 0-1 BFS: deque (double-ended queue). For edge weight 0: push neighbor to front (same distance). For edge weight 1: push neighbor to back (distance+1). Front always has minimum distance node.
// Multi-source BFS: find distance from nearest source to every cell
function multiSourceBFS(grid, sources) {
const m = grid.length, n = grid[0].length;
const dist = Array.from({length: m}, () => new Array(n).fill(Infinity));
const queue = [];
// Initialize all sources with distance 0
for (const [r, c] of sources) { dist[r][c] = 0; queue.push([r, c]); }
const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
while (queue.length) {
const [r, c] = queue.shift();
for (const [dr, dc] of dirs) {
const [nr, nc] = [r+dr, c+dc];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] === Infinity) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
return dist;
}
// 0-1 BFS: edge weights are 0 or 1, use deque
function zerOneeBFS(n, edges, src) {
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
const deque = [src]; // front = minimum dist
while (deque.length) {
const u = deque.shift();
for (const [v, w] of (edges[u] || [])) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w === 0) deque.unshift(v); // same dist, push to front
else deque.push(v); // dist+1, push to back
}
}
}
return dist;
}0-1 BFS guarantee: Deque front always contains the current minimum-distance node (proof: weight-0 edges don't increase distance, so front stays minimum). O(V+E) vs Dijkstra's O(E log V).
When to use 0-1 BFS: Costs are exactly 0 or 1. Common disguises: "changing direction costs 1", "passing through a wall costs 1 health", "free moves vs paid moves".