Многоисточниковый BFS: Rotting Oranges, 01 Matrix и Walls and Gates

Multi-source BFS простыми словами: как за один обход найти расстояние до ближайшего объекта и решить Rotting Oranges, 01 Matrix и Walls and Gates. Шаблон и код на Python.

11 мин чтенияалгоритмы · графы · bfs · python

Коротко

ЧтоОтвет
ЗадачаДля каждой клетки (вершины) найти расстояние до ближайшего из нескольких источников
ИдеяПоложить в очередь все источники сразу с расстоянием 0 и запустить один обычный BFS
СложностьO(V+E)O(V + E), для сетки m×nm \times n — O(mn)O(mn) по времени и памяти
НаивноBFS из каждого источника или из каждой клетки — O(k⋅mn)O(k \cdot mn) или O((mn)2)O((mn)^2)
Типичные задачиRotting Oranges, 01 Matrix, Walls and Gates, As Far from Land as Possible, Shortest Bridge

Если вы уже знаете обычный BFS, то многоисточниковый — это одна строчка разницы: очередь инициализируется не одной вершиной, а списком. Вся хитрость в том, чтобы понять, почему это корректно и в каких задачах эта строчка спасает от TLE.

Интуиция: пожар, который начинается в нескольких местах

Представьте поле сухой травы, которое подожгли одновременно в трёх точках. Каждую минуту огонь перекидывается на соседние клетки. Через сколько минут загорится конкретная клетка? Ровно через столько, сколько шагов до ближайшего очага: какой фронт дойдёт первым, тот её и подожжёт.

BFS моделирует именно такое распространение. Обычный BFS — пожар из одной точки: сначала горят клетки на расстоянии 1, потом 2, потом 3. Многоисточниковый — пожар из нескольких точек одновременно. Фронты растут синхронно, а когда встречаются, клетка уже помечена как посещённая, и второй фронт её не трогает.

Формальнее это выглядит так. Добавим в граф фиктивную вершину SS — «суперисточник» — и проведём из неё рёбра веса 0 во все настоящие источники. Тогда

dist(v)=min⁡s∈sourcesd(s,v)=d(S,v)\text{dist}(v) = \min_{s \in \text{sources}} d(s, v) = d(S, v)

То есть расстояние до ближайшего источника — это обычное кратчайшее расстояние от одной вершины SS. Запуск BFS из SS первым шагом достанет из очереди SS и положит туда все источники с расстоянием 0. Многоисточниковый BFS просто пропускает этот первый шаг: суперисточник нигде не создаётся, источники сразу кладутся в очередь.

Из этого рассуждения следует главное: корректность гарантирована теми же свойствами, что и у обычного BFS. Очередь в любой момент содержит вершины не более чем двух соседних уровней, расстояния выдаются в неубывающем порядке, и первая пометка вершины — окончательная.

Наивное решение и почему оно плохое

Возьмём задачу 01 Matrix (LeetCode 542): дана матрица из нулей и единиц, для каждой клетки нужно найти расстояние до ближайшего нуля (по манхэттену, шагами вверх/вниз/влево/вправо).

Первое, что приходит в голову, — для каждой единицы запустить BFS и искать ближайший ноль:

from collections import deque def update_matrix_naive(mat): rows, cols = len(mat), len(mat[0]) res = [[0] * cols for _ in range(rows)] for r in range(rows): for c in range(cols): if mat[r][c] == 0: continue seen = {(r, c)} q = deque([(r, c, 0)]) while q: x, y, d = q.popleft() if mat[x][y] == 0: res[r][c] = d break for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): nx, ny = x + dx, y + dy if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in seen: seen.add((nx, ny)) q.append((nx, ny, d + 1)) return res

Работает, но в худшем случае (один ноль в углу, остальное — единицы) каждый BFS обходит почти всю матрицу. Это O((mn)2)O((mn)^2): при ограничении mn≤104mn \le 10^4 получается порядка 10810^8 операций, и на Python это гарантированный TLE.

Вторая идея — запустить BFS из каждого нуля и брать минимум. Тоже плохо: если нулей kk, то O(k⋅mn)O(k \cdot mn), а нулей может быть половина матрицы.

Оба подхода делают одну и ту же ошибку: много раз заново исследуют одни и те же клетки. Многоисточниковый BFS посещает каждую клетку ровно один раз.

Шаблон

from collections import deque def multi_source_bfs(graph, sources): dist = {s: 0 for s in sources} queue = deque(sources) while queue: v = queue.popleft() for u in graph[v]: if u not in dist: dist[u] = dist[v] + 1 queue.append(u) return dist

Отличие от обычного BFS только в двух первых строках. Всё остальное — стандартный обход: берём вершину из начала очереди, смотрим соседей, непосещённым ставим расстояние на единицу больше и кладём в конец.

Важная деталь: вершину помечаем в момент добавления в очередь, а не в момент извлечения. Иначе одна и та же клетка может попасть в очередь несколько раз от разных соседей, и на сетке это раздувает очередь в разы.

01 Matrix (LeetCode 542)

Источники — все нули. Расстояние до ближайшего нуля у самого нуля равно 0, у остальных клеток — то, что посчитает BFS.

from collections import deque def update_matrix(mat): rows, cols = len(mat), len(mat[0]) dist = [[-1] * cols for _ in range(rows)] queue = deque() for r in range(rows): for c in range(cols): if mat[r][c] == 0: dist[r][c] = 0 queue.append((r, c)) while queue: r, c = queue.popleft() for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 queue.append((nr, nc)) return dist print(update_matrix([[0, 0, 0], [0, 1, 0], [1, 1, 1]])) # [[0, 0, 0], [0, 1, 0], [1, 2, 1]]

Матрица dist с -1 одновременно служит и ответом, и множеством посещённых клеток. Отдельный visited не нужен.

Разбор на примере

mat:        шаг 0:      шаг 1:      шаг 2:
0 0 0       0 0 0       0 0 0       0 0 0
0 1 0       0 . 0       0 1 0       0 1 0
1 1 1       . . .       1 . 1       1 2 1

На старте в очереди пять нулей. Из них BFS дотягивается до центральной клетки и до двух крайних клеток нижнего ряда — они получают 1. Центральная клетка нижнего ряда соседствует только с клетками уровня 1, поэтому получает 2. Каждую клетку мы посетили один раз.

Альтернатива: два прохода DP

У 01 Matrix есть известное решение без очереди: проход сверху-слева вниз-вправо, где dist[r][c] = min(dist[r-1][c], dist[r][c-1]) + 1, и обратный проход снизу-справа. Оно тоже O(mn)O(mn) и экономит очередь, но работает только для сетки с 4-связностью без препятствий. Многоисточниковый BFS обобщается на стены, произвольные графы и другие типы соседства, поэтому на собеседовании я бы начинал с него, а DP упомянул как вариант.

Rotting Oranges (LeetCode 994)

Сетка: 0 — пусто, 1 — свежий апельсин, 2 — гнилой. Каждую минуту гниль переходит на соседние свежие апельсины. Сколько минут пройдёт, пока не сгниют все? Если это невозможно, вернуть -1.

Это ровно «пожар из нескольких очагов». Источники — гнилые апельсины. Ответ — номер последнего слоя BFS. Здесь удобно обходить очередь слоями: снимаем ровно len(queue) элементов — это одна минута.

from collections import deque def oranges_rotting(grid): rows, cols = len(grid), len(grid[0]) queue = deque() fresh = 0 for r in range(rows): for c in range(cols): if grid[r][c] == 2: queue.append((r, c)) elif grid[r][c] == 1: fresh += 1 minutes = 0 while queue and fresh > 0: for _ in range(len(queue)): # один слой = одна минута r, c = queue.popleft() for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1: grid[nr][nc] = 2 # помечаем при добавлении fresh -= 1 queue.append((nr, nc)) minutes += 1 return minutes if fresh == 0 else -1 print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]])) # 4 print(oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]])) # -1 print(oranges_rotting([[0, 2]])) # 0

Тонкие места этой задачи:

  • Условие fresh > 0 в while. Без него счётчик минут увеличится ещё раз после того, как последний слой уже ничего не заразил, и ответ будет на 1 больше. Альтернатива — вернуть max(minutes - 1, 0), но так легче ошибиться.
  • Свежих апельсинов нет изначально. Ответ 0, даже если гнилых тоже нет. Счётчик fresh обрабатывает это автоматически.
  • Изолированный свежий апельсин. BFS закончится, а fresh останется больше нуля — возвращаем -1. Отдельный обход «проверить, остались ли единицы» не нужен.
  • Мутация входа. Мы портим grid. На LeetCode это допустимо, на собеседовании стоит сказать вслух и предложить скопировать сетку, если вход нельзя менять.

Walls and Gates (LeetCode 286)

Задача из премиум-раздела, но её любят давать на интервью. Сетка комнат: -1 — стена, 0 — ворота, INF (2**31 - 1) — пустая комната. Нужно заполнить каждую пустую комнату расстоянием до ближайших ворот; недостижимые остаются INF.

Источники — ворота. Значение INF само работает как флаг «не посещено», а стены просто никогда не проходят проверку.

from collections import deque INF = 2**31 - 1 def walls_and_gates(rooms): if not rooms: return rows, cols = len(rooms), len(rooms[0]) queue = deque( (r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0 ) while queue: r, c = queue.popleft() for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF: rooms[nr][nc] = rooms[r][c] + 1 queue.append((nr, nc)) rooms = [ [INF, -1, 0, INF], [INF, INF, INF, -1], [INF, -1, INF, -1], [0, -1, INF, INF], ] walls_and_gates(rooms) print(rooms) # [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

Посмотрите на клетку (1, 1): до верхних ворот (0, 2) от неё 2 шага, до нижних (3, 0) — 3. BFS записал 2, потому что волна от верхних ворот добралась туда раньше. Никакого min в коде нет — минимум обеспечивает порядок обхода.

Частая ошибка в этой задаче — запускать DFS из каждых ворот с обновлением rooms[nr][nc] = min(...). Это работает, но DFS не гарантирует, что первое найденное расстояние минимальное, поэтому клетки перезаписываются много раз, и в худшем случае время растёт до O(k⋅mn)O(k \cdot mn).

As Far from Land as Possible (LeetCode 1162)

Сетка n × n из воды (0) и суши (1). Найти клетку воды, у которой расстояние до ближайшей суши максимально, и вернуть это расстояние. Если суши или воды нет, вернуть -1.

Это 01 Matrix «наоборот»: источники — суша, ответ — максимум по всем расстояниям, то есть номер последнего слоя.

from collections import deque def max_distance(grid): n = len(grid) queue = deque((r, c) for r in range(n) for c in range(n) if grid[r][c] == 1) if len(queue) in (0, n * n): return -1 dist = -1 while queue: for _ in range(len(queue)): r, c = queue.popleft() for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0: grid[nr][nc] = 1 queue.append((nr, nc)) dist += 1 return dist print(max_distance([[1, 0, 1], [0, 0, 0], [1, 0, 1]])) # 2 print(max_distance([[1, 0, 0], [0, 0, 0], [0, 0, 0]])) # 4

Здесь dist стартует с -1, потому что последний слой ничего не добавляет в очередь, но счётчик всё равно увеличивается. Тот же эффект, что в Rotting Oranges, только решённый другим способом. Выберите один и используйте его везде, чтобы не путаться.

Не только расстояние: кто ближайший

Иногда нужно знать не только расстояние до ближайшего источника, но и какой это источник. Например, «для каждого дома найти ближайшую больницу» или «разбить карту на зоны влияния магазинов» (дискретный аналог диаграммы Вороного). Достаточно протащить вместе с расстоянием метку источника:

from collections import deque def nearest_source(graph, sources): owner = {s: s for s in sources} dist = {s: 0 for s in sources} queue = deque(sources) while queue: v = queue.popleft() for u in graph[v]: if u not in dist: dist[u] = dist[v] + 1 owner[u] = owner[v] queue.append(u) return dist, owner g = {"A": ["B"], "B": ["A", "C"], "C": ["B", "D"], "D": ["C", "E"], "E": ["D"]} print(nearest_source(g, ["A", "E"])) # ({'A': 0, 'E': 0, 'B': 1, 'D': 1, 'C': 2}, # {'A': 'A', 'E': 'E', 'B': 'A', 'D': 'E', 'C': 'A'})

Вершина C равноудалена от A и E и досталась A, потому что A стоял в очереди первым. Если в задаче важно, как разрешать ничьи, это надо обработать явно: например, при встрече фронтов разных источников на одном уровне помечать клетку как спорную.

Та же идея с метками лежит в основе задачи Shortest Bridge (LeetCode 934): сначала DFS-ом или заливкой помечаем все клетки первого острова, кладём их в очередь как источники и BFS-ом расширяемся по воде, пока не упрёмся во второй остров.

Сложность

Каждая вершина попадает в очередь не больше одного раза, каждое ребро просматривается не больше двух раз (в неориентированном графе). Итого:

  • время — O(V+E)O(V + E); для сетки m×nm \times n с 4-связностью это O(mn)O(mn);
  • память — O(V)O(V) на очередь и массив расстояний; для сетки — O(mn)O(mn). Если разрешено менять вход, массив расстояний можно хранить прямо в нём, как в Walls and Gates.

Количество источников kk на сложность не влияет: начальная загрузка очереди стоит O(k)≤O(V)O(k) \le O(V).

Когда многоисточниковый BFS не подходит

  • Рёбра разного веса. BFS опирается на то, что все рёбра стоят одинаково. Если веса 0 и 1, берите 0-1 BFS — там тоже можно стартовать с нескольких источников. Для произвольных неотрицательных весов — Дейкстра, в которой в начальную кучу кладутся все источники с расстоянием 0. Трюк с суперисточником работает для любого алгоритма кратчайших путей.
  • Нужно расстояние до самого дальнего источника или сумма расстояний до всех источников. Тогда минимум не помогает, и придётся считать BFS из каждого источника отдельно. Пример — Shortest Distance from All Buildings (LeetCode 317).
  • Нужен путь между двумя конкретными точками. Это обычный BFS или, если граф большой, двунаправленный BFS. Двунаправленный BFS иногда путают с многоисточниковым: там два фронта идут навстречу друг другу, чтобы встретиться, а здесь несколько фронтов делят граф между собой.

Типичные ошибки

  1. Пометка при извлечении, а не при добавлении. Клетка попадает в очередь несколько раз, время и память растут, а в задачах со слоями (Rotting Oranges) ещё и ломается подсчёт.
  2. Запуск BFS по очереди из каждого источника в одном цикле for s in sources: bfs(s) с общим visited. Первый источник «захватит» всю компоненту, и расстояния будут до него, а не до ближайшего. Все источники должны стартовать одновременно.
  3. Off-by-one в подсчёте слоёв. Последний слой ничего не добавляет, но счётчик увеличивается. Проверьте решение на сетке без свежих апельсинов и на сетке из одной клетки.
  4. Забыть про недостижимые клетки. В Rotting Oranges это -1, в Walls and Gates — оставить INF, в 01 Matrix по условию гарантирован хотя бы один ноль. Прочитайте ограничения.
  5. Использовать list.pop(0) вместо deque.popleft(). Первое — O(n)O(n), и на сетке 100×100100 \times 100 это уже заметно. Подробнее про очереди в Python — в статье про модуль collections.
  6. Рекурсивный DFS вместо BFS. DFS не даёт кратчайших расстояний и на больших сетках упирается в лимит рекурсии Python.

Как это выглядит на собеседовании

Многоисточниковый BFS почти никогда не называют прямо. Сигналы в условии:

  • «расстояние до ближайшего X» для каждой клетки;
  • процесс, который одновременно распространяется из нескольких мест (гниль, огонь, вирус, вода);
  • «минимальное время, пока всё не заполнится».

Хороший ход — сначала озвучить наивное решение с BFS из каждой клетки, оценить его в O((mn)2)O((mn)^2) и затем перевернуть задачу: «вместо того чтобы из каждой клетки искать ближайший источник, пустим волну из всех источников сразу». Интервьюеры ценят именно этот переворот — он показывает, что вы понимаете, откуда берётся оптимизация, а не помните шаблон.

Частые фоллоуапы:

  • Почему расстояния получаются минимальными? — Аргумент с суперисточником: это обычный BFS из одной фиктивной вершины.
  • А если у клеток разная стоимость прохода? — Дейкстра с несколькими стартовыми вершинами в куче.
  • А если сетка огромная и не помещается в память? — Обход по слоям хранит только текущий фронт и множество посещённых; можно говорить о хранении сетки по частям, но это уже скорее разговор о системах.
  • Можно ли без очереди? — Для 01 Matrix да: два прохода DP.

Итог

Многоисточниковый BFS — это обычный BFS, у которого в очереди на старте лежат все источники. Он считает расстояние до ближайшего объекта для всех вершин за один проход, O(V+E)O(V + E), вместо kk отдельных обходов. Запомните три вещи: все источники стартуют одновременно, помечайте при добавлении в очередь, а если нужны «минуты» — обходите слоями и следите за off-by-one. С этим набором закрываются Rotting Oranges, 01 Matrix, Walls and Gates, As Far from Land as Possible и половина задач Shortest Bridge.

Потренироваться в спокойной обстановке

Все задачи