Multi-Source BFS | Multiple Starting Points | Queue

Overview

Multi-source BFS is a variation of BFS where you start from multiple source nodes simultaneously instead of a single source. All sources are added to the queue at the beginning, and BFS explores from all of them concurrently, ensuring that the first time any node is reached is via the shortest path from the nearest source.

Multi-source BFS is particularly powerful for problems where you need to find distances from multiple starting points, such as "rotting oranges" (multiple rotten oranges spreading), "walls and gates" (multiple gates filling rooms), or finding the nearest source to each node. It's essentially running BFS from multiple sources in parallel.

Key characteristics:

Multiple sources - Start BFS from multiple nodes simultaneously
Parallel exploration - Explore from all sources concurrently
Shortest distance - Finds shortest distance to nearest source
Level-by-level - Still processes level by level
Queue initialization - All sources added to queue initially

How Multi-Source BFS Works

Multi-source BFS follows these steps:

Initialize - Add all source nodes to queue and mark as visited
Set distance - Set distance of sources to 0 (or their initial value)
While queue is not empty:

Dequeue a node
Process the node
Enqueue all unvisited neighbors
Set neighbor distance = current distance + 1
Mark neighbors as visited

Repeat until queue is empty

The key difference from regular BFS is starting with multiple sources in the queue.

Basic Multi-Source BFS

Find shortest distance from any source to all nodes:

function multiSourceBFS(graph: number[][], sources: number[]): number[] {
  const n = graph.length;
  const dist = new Array(n).fill(Infinity);
  const visited = new Set<number>();
  const queue: number[] = [];
  
  // Initialize all sources
  for (const source of sources) {
    queue.push(source);
    dist[source] = 0;
    visited.add(source);
  }
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        dist[neighbor] = dist[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  
  return dist;
}

Time: O(V + E), Space: O(V)

Key insight: All sources start at distance 0 and explore simultaneously.

Pattern 1: Rotting Oranges

Find time for all oranges to rot (multi-source BFS from rotten oranges):

function orangesRotting(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue: [number, number][] = [];
  let freshCount = 0;
  
  // Find all rotten oranges (sources)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) {
        queue.push([r, c]);
      } else if (grid[r][c] === 1) {
        freshCount++;
      }
    }
  }
  
  if (freshCount === 0) return 0;
  
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  let minutes = 0;
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    
    // Process all oranges at current minute
    for (let i = 0; i < levelSize; i++) {
      const [r, c] = queue.shift()!;
      
      // Rot neighboring fresh oranges
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        
        if (
          nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          grid[nr][nc] === 1
        ) {
          grid[nr][nc] = 2;
          freshCount--;
          queue.push([nr, nc]);
        }
      }
    }
    
    minutes++;
  }
  
  return freshCount === 0 ? minutes - 1 : -1;
}

Time: O(rows × cols), Space: O(rows × cols)

Key insight: All rotten oranges start rotting simultaneously.

Pattern 2: Walls and Gates

Fill rooms with distance to nearest gate:

function wallsAndGates(rooms: number[][]): void {
  const rows = rooms.length;
  const cols = rooms[0].length;
  const queue: [number, number][] = [];
  
  // Find all gates (sources)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rooms[r][c] === 0) {
        queue.push([r, c]);
      }
    }
  }
  
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  
  while (queue.length > 0) {
    const [r, c] = queue.shift()!;
    
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        rooms[nr][nc] === 2147483647 // INF
      ) {
        rooms[nr][nc] = rooms[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
}

Time: O(rows × cols), Space: O(rows × cols)

Key insight: All gates start filling rooms simultaneously.

Pattern 3: Shortest Distance from Multiple Buildings

Find shortest distance from any building to empty land:

function shortestDistance(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const buildings: [number, number][] = [];
  
  // Find all buildings
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) {
        buildings.push([r, c]);
      }
    }
  }
  
  // For each building, run BFS and accumulate distances
  const dist = new Array(rows).fill(0).map(() => 
    new Array(cols).fill(0)
  );
  const reachable = new Array(rows).fill(0).map(() => 
    new Array(cols).fill(0)
  );
  
  for (let i = 0; i < buildings.length; i++) {
    const queue: [number, number, number][] = [[buildings[i][0], buildings[i][1], 0]];
    const visited = new Set<string>();
    
    while (queue.length > 0) {
      const [r, c, d] = queue.shift()!;
      const key = `${r},${c}`;
      
      if (visited.has(key)) continue;
      visited.add(key);
      
      if (grid[r][c] === 0) {
        dist[r][c] += d;
        reachable[r][c]++;
      }
      
      const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        
        if (
          nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          grid[nr][nc] === 0 &&
          !visited.has(`${nr},${nc}`)
        ) {
          queue.push([nr, nc, d + 1]);
        }
      }
    }
  }
  
  // Find minimum distance
  let minDist = Infinity;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 0 && reachable[r][c] === buildings.length) {
        minDist = Math.min(minDist, dist[r][c]);
      }
    }
  }
  
  return minDist === Infinity ? -1 : minDist;
}

Time: O(rows × cols × buildings), Space: O(rows × cols)

Note: This runs BFS from each building separately, not true multi-source BFS.

Pattern 4: 0-1 Matrix (Distance to Nearest Zero)

Find distance from each cell to nearest zero:

function updateMatrix(mat: number[][]): number[][] {
  const rows = mat.length;
  const cols = mat[0].length;
  const queue: [number, number][] = [];
  const result = new Array(rows).fill(0).map(() => 
    new Array(cols).fill(Infinity)
  );
  
  // Find all zeros (sources)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (mat[r][c] === 0) {
        queue.push([r, c]);
        result[r][c] = 0;
      }
    }
  }
  
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  
  while (queue.length > 0) {
    const [r, c] = queue.shift()!;
    
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        result[nr][nc] === Infinity
      ) {
        result[nr][nc] = result[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
  
  return result;
}

Time: O(rows × cols), Space: O(rows × cols)

Key insight: All zeros start at distance 0.

Pattern 5: As Far from Land as Possible

Find water cell farthest from any land:

function maxDistance(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue: [number, number][] = [];
  
  // Find all land cells (sources)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) {
        queue.push([r, c]);
      }
    }
  }
  
  if (queue.length === 0 || queue.length === rows * cols) return -1;
  
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  let maxDist = 0;
  
  while (queue.length > 0) {
    const [r, c] = queue.shift()!;
    
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        grid[nr][nc] === 0
      ) {
        grid[nr][nc] = grid[r][c] + 1;
        maxDist = Math.max(maxDist, grid[nr][nc] - 1);
        queue.push([nr, nc]);
      }
    }
  }
  
  return maxDist;
}

Time: O(rows × cols), Space: O(rows × cols)

Key insight: Track maximum distance during BFS.

Pattern 6: Shortest Bridge

Find shortest path between two islands (multi-source from first island):

function shortestBridge(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue: [number, number][] = [];
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  
  // Find first island and mark it
  function dfs(r: number, c: number): void {
    if (
      r < 0 || r >= rows ||
      c < 0 || c >= cols ||
      grid[r][c] !== 1
    ) return;
    
    grid[r][c] = 2; // Mark as visited
    queue.push([r, c]); // Add to queue for BFS
    
    for (const [dr, dc] of directions) {
      dfs(r + dr, c + dc);
    }
  }
  
  // Find first island
  let found = false;
  for (let r = 0; r < rows && !found; r++) {
    for (let c = 0; c < cols && !found; c++) {
      if (grid[r][c] === 1) {
        dfs(r, c);
        found = true;
      }
    }
  }
  
  // Multi-source BFS from first island
  let steps = 0;
  while (queue.length > 0) {
    const levelSize = queue.length;
    
    for (let i = 0; i < levelSize; i++) {
      const [r, c] = queue.shift()!;
      
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        
        if (
          nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          grid[nr][nc] !== 2
        ) {
          if (grid[nr][nc] === 1) {
            return steps;
          }
          grid[nr][nc] = 2;
          queue.push([nr, nc]);
        }
      }
    }
    
    steps++;
  }
  
  return -1;
}

Time: O(rows × cols), Space: O(rows × cols)

Key insight: Mark first island, then BFS from all its cells.

Pattern 7: Nearest Exit from Entrance

Find nearest exit from entrance (multi-source from entrance cells):

function nearestExit(maze: string[][], entrance: number[]): number {
  const rows = maze.length;
  const cols = maze[0].length;
  const queue: [number, number, number][] = [[entrance[0], entrance[1], 0]];
  const visited = new Set<string>([`${entrance[0]},${entrance[1]}`]);
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  
  while (queue.length > 0) {
    const [r, c, steps] = queue.shift()!;
    
    // Check if exit (boundary and not entrance)
    if (
      (r === 0 || r === rows - 1 || c === 0 || c === cols - 1) &&
      !(r === entrance[0] && c === entrance[1])
    ) {
      return steps;
    }
    
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;
      
      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        maze[nr][nc] === '.' &&
        !visited.has(key)
      ) {
        visited.add(key);
        queue.push([nr, nc, steps + 1]);
      }
    }
  }
  
  return -1;
}

Time: O(rows × cols), Space: O(rows × cols)

Note: Single source here, but pattern similar.

When to Use Multi-Source BFS

Use multi-source BFS when you see these signals:

"Multiple sources" - Start from multiple points simultaneously
"Nearest source" - Find distance to nearest of multiple sources
"Simultaneous spread" - Multiple points spreading at same time
"Rotting/spreading" - Multiple sources causing spread
"Gates/entrances" - Multiple entry points
"Shortest from any" - Shortest distance from any source
"Parallel exploration" - Explore from multiple starting points

Key distinction:

Multi-source BFS - Start from multiple sources simultaneously
Regular BFS - Start from single source
Multiple BFS calls - Run BFS separately from each source

Multi-Source BFS vs Regular BFS

| Aspect | Multi-Source BFS | Regular BFS |

|--------|-----------------|-------------|

| Sources | Multiple sources | Single source |

| Initialization | Add all sources to queue | Add one source to queue |

| Distance | Distance to nearest source | Distance from single source |

| Use case | Rotting oranges, walls and gates | Single-source shortest path |

| Complexity | Same O(V + E) | O(V + E) |

Remember:

Multi-source BFS for multiple starting points, nearest source problems
Regular BFS for single-source shortest path

Template (Basic Multi-Source BFS)

function multiSourceBFSTemplate(graph: number[][], sources: number[]): number[] {
  const n = graph.length;
  const dist = new Array(n).fill(Infinity);
  const visited = new Set<number>();
  const queue: number[] = [];
  
  // Initialize all sources
  for (const source of sources) {
    queue.push(source);
    dist[source] = 0;
    visited.add(source);
  }
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        dist[neighbor] = dist[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  
  return dist;
}

Template (2D Grid Multi-Source BFS)

function multiSourceBFS2DTemplate(
  grid: number[][],
  sources: [number, number][]
): number[][] {
  const rows = grid.length;
  const cols = grid[0].length;
  const dist = new Array(rows).fill(0).map(() => 
    new Array(cols).fill(Infinity)
  );
  const queue: [number, number][] = [];
  
  // Initialize all sources
  for (const [r, c] of sources) {
    queue.push([r, c]);
    dist[r][c] = 0;
  }
  
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  
  while (queue.length > 0) {
    const [r, c] = queue.shift()!;
    
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        dist[nr][nc] === Infinity
      ) {
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
  
  return dist;
}

Time and Space Complexity

Graph Multi-Source BFS

Time: O(V + E) where V is vertices, E is edges
Space: O(V) for queue and visited set

2D Grid Multi-Source BFS

Time: O(rows × cols)
Space: O(rows × cols)

Note: Complexity is same as regular BFS because we still visit each node once.

Practice Tips

Initialize all sources - Add all sources to queue at start
Set source distances - Set distance of sources to 0 (or initial value)
Level-by-level - Still process level by level for time tracking
Mark visited - Mark sources as visited when adding to queue
Track distance - Update distance when visiting neighbors
2D grids - Use direction vectors for up/down/left/right
Early termination - Can return early when target found

Common Mistakes

Not initializing all sources - Missing some sources in queue
Wrong initial distance - Not setting source distances to 0
Not marking sources visited - Sources revisited
Wrong distance update - Not updating distance correctly
Level tracking - Forgetting to track level size for time problems
Boundary checks - Not checking grid boundaries in 2D problems
Visited set - Not using visited set or using incorrectly

Real-World Applications

Multi-source BFS is used extensively in:

Disease Spread - Multiple infection sources spreading
Network Routing - Multiple routers broadcasting
Game AI - Multiple units exploring simultaneously
Image Processing - Flood fill from multiple seeds
Social Networks - Multiple users spreading information
Epidemiology - Multiple outbreak locations
Resource Distribution - Multiple distribution centers
Sensor Networks - Multiple sensors broadcasting

Related Concepts

Breadth-First Search (BFS) - Foundation for multi-source BFS
Shortest Path - Multi-source finds shortest to nearest source
Level-Order Traversal - Similar level-by-level processing
Flood Fill - Similar concept for filling regions
Graph Traversal - General graph exploration

Summary

Multi-source BFS is a powerful variation of BFS:

Multiple sources - Start from multiple nodes simultaneously
Parallel exploration - Explore from all sources concurrently
Shortest distance - Finds shortest distance to nearest source
Same complexity - O(V + E) time, O(V) space
Essential - For rotting/spreading problems, nearest source problems

Key takeaways:

Initialize queue with all sources
Set source distances to 0
Process level by level for time tracking
Essential for problems with multiple starting points
More efficient than running BFS separately from each source

Mastering multi-source BFS will help you solve rotting oranges, walls and gates, and nearest source problems efficiently in coding interviews.