Multi-source BFS

19.07.2023 — Algorithms — 1 min read

Overview

This pattern is a variation of a BFS graph traversal. The main difference between multi-source and classic BFS is that in multi-source BFS we start from several nodes at the same time.

Usage

We first need to identify nodes in the graph based on some condition according to the problem (this could be node's value == 1). Then we push these nodes in the queue and perform classic BFS from these nodes. This version of BFS will spread across the graph from these nodes and is helpful when we need to find min/max spread times across the grid, etc.

Example

It's generally useful when the problem requires some kind of spreading across the graph. The rotting oranges problem would a classic problem for this pattern.

See the solution below:

1def orangesRotting(self, grid: List[List[int]]) -> int:
2        m, n = len(grid), len(grid[0])
3        def in_bounds(row, col) -> bool:
4            return row >= 0 and row < m and col >= 0 and col < n
5
6        directions = [[0,1], [1,0], [0,-1], [-1,0]]
7        fresh = level = 0
8        q = deque()
9        for i in range(m):
10            for j in range(n):
11                if grid[i][j] == 1:
12                    fresh += 1
13                if grid[i][j] == 2:
14                    q.append((i, j))
15
16        while q:
17            level += 1
18            for _ in range(len(q)):
19                row, col = q.popleft()
20                for dx, dy in directions:
21                    n_row, n_col = row + dx, col + dy
22                    if in_bounds(n_row, n_col) and grid[n_row][n_col] == 1:
23                        q.append((n_row, n_col))
24                        grid[n_row][n_col] = 2
25                        fresh -= 1
26        return max(level-1, 0) if fresh == 0 else -1