BFS / DFS

Multi-Source BFS

Start BFS from multiple nodes simultaneously — enqueue ALL sources at the start. The BFS wavefront expands from all sources at once. Solves 'distance to nearest source' problems like Rotting Oranges.

O(V + E)

O(V)

How It Works

Multi-source BFS answers 'how far is each cell from the nearest source' by seeding the queue with every source at once, all at distance 0. The wavefronts from all sources expand simultaneously, and each node is claimed by whichever source reaches it first. Since BFS processes nodes in order of distance, the first visit to any node records its distance to the closest source — no per-source comparison needed.

The naive alternative runs a separate BFS from each of k sources and takes the minimum, costing O(k(V + E)). Multi-source BFS does one traversal in O(V + E) regardless of how many sources there are, because each node is still visited exactly once. It is the standard tool for spreading processes like rotting oranges, fire spread, or distance-to-nearest-obstacle maps.

Step-by-Step Visualization

Rotting oranges: 2=rotten, 1=fresh, 0=empty

Sources1 rotten orange

Fresh7

1/4

Code

Java

static int orangesRotting(int[][] grid) {
  Queue<int[]> queue = new LinkedList<>();
  int fresh = 0;

  for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++) {
      if (grid[r][c] == 2) queue.add(new int[]{r, c, 0});
      else if (grid[r][c] == 1) fresh++;
    }

  int time = 0;
  int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
  while (!queue.isEmpty()) {
    int[] curr = queue.poll();
    int r = curr[0], c = curr[1], t = curr[2];
    for (int[] d : dirs) {
      int nr = r+d[0], nc = c+d[1];
      if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 1) {
        grid[nr][nc] = 2;
        fresh--;
        queue.add(new int[]{nr, nc, t+1});
        time = t + 1;
      }
    }
  }
  return fresh == 0 ? time : -1;
}

Tips & Gotchas

1Enqueue ALL source nodes at the start (distance 0)

2BFS expands from all sources simultaneously

3Like dropping stones in water — waves expand from all sources

Practice Problems

1Rotting Oranges
201 Matrix
3Walls and Gates
4Map of Highest Peak

About the BFS / DFS Pattern

The two fundamental ways to explore a graph. DFS goes as deep as possible before backtracking (uses a stack or recursion). BFS explores all neighbors first before going deeper (uses a queue). Both visit every node exactly once.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

How is multi-source BFS different from running BFS from each source?

Functionally it computes the same nearest-source distances, but it does so in a single O(V + E) pass instead of k separate traversals. Conceptually you can imagine a virtual super-source connected to all real sources with zero-weight edges.

How do I track elapsed time or rounds, as in Rotting Oranges?

Process the queue level by level: record the queue size at the start of each round, dequeue exactly that many nodes, and increment a timer after each round. Alternatively, store the distance alongside each node when enqueuing it.