Поиск в ширину (BFS)

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

Граф из вершин, обозначенных буквами и раскрашенных кольцами по расстоянию от стартовой вершины, с очередью вершин внизу
Граф из вершин, обозначенных буквами и раскрашенных кольцами по расстоянию от стартовой вершины, с очередью вершин внизу

Идея

Граф — это множество вершин, соединенных ребрами: места и дороги, люди и дружеские связи, клетки лабиринта и проходы между ними. Поиск в ширину отвечает на вопрос: куда я могу попасть отсюда и за какое наименьшее число шагов? Он хранит очередь вершин, которые еще предстоит посетить. Вершины берутся из начала, а новые добавляются в конец, поэтому вершины обрабатываются в том порядке, в котором были обнаружены.

Шаг за шагом

Поместите старт в очередь с расстоянием 0. Возьмите вершину из начала очереди. Для каждого соседа, которого еще не видели, запишите расстояние на единицу больше, чем у текущей вершины, запомните текущую вершину как ту, из которой в него пришли, и добавьте его в конец очереди. Уже встречавшихся соседей пропускайте. Повторяйте, пока очередь не опустеет или пока не будет достигнута цель.

Пример

Возьмем граф с ребрами A–B, A–C, B–D, C–D, C–E и D–F и начнем с вершины A. Когда A берется из очереди, находятся B и C на расстоянии 1. Вершина B дает D на расстоянии 2. Вершина C обнаруживает, что D уже встречалась, и находит E на расстоянии 2. Вершина D дает F на расстоянии 3. E и F не находят ничего нового, и очередь пустеет. Если пройти по запомненным вершинам назад от F, получится F ← D ← B ← A, так что кратчайший путь из A в F — это A → B → D → F длиной в три ребра.

Почему расстояния верны

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

История и применение

Конрад Цузе описал поиск в ширину в 1945 году в работе над своим языком Plankalkül, которая была опубликована лишь в 1972 году. Эдвард Ф. Мур заново изобрел его в 1959 году, чтобы найти кратчайший выход из лабиринта, а Ч. Ли в 1961 году применил его для трассировки проводников на печатных платах. Сегодня он находит наименьшее число ходов в головоломках, степени разделения в социальных сетях, страницы, до которых веб-краулер доходит первыми, и ближайшую свободную клетку в играх. Когда у ребер есть длины, его обобщает алгоритм Дейкстры.

Конрад Цузе (в центре, в очках) и Хайнц Биллинг (слева) на выставке SYSTEMS ’91 в Мюнхене. Цузе описал поиск в ширину в 1945 году в работах по языку Plankalkül, опубликованных лишь в 1972.
Конрад Цузе (в центре, в очках) и Хайнц Биллинг (слева) на выставке SYSTEMS ’91 в Мюнхене. Цузе описал поиск в ширину в 1945 году в работах по языку Plankalkül, опубликованных лишь в 1972.

Попробуйте сами

Откройте приложение и нажмите Шаг. Вершина, которую сейчас посещают, выделена, вершины, ждущие в очереди, синие, а посещенные — зеленые, и на каждой указано расстояние. Очередь показана под графом, начало — первым. Переключите щелчок на Цель и выберите вершину, чтобы остановиться на ней и увидеть кратчайший путь, или создайте новый граф с большим числом вершин и ребер.

Часто задаваемые вопросы

Какова временная сложность BFS?

O(V + E) для V вершин (vertices) и E ребер (edges): каждая вершина один раз попадает в очередь и один раз покидает ее, а каждое ребро проверяется с обоих концов. Нужно O(V) дополнительной памяти на очередь и расстояния.

Почему BFS использует очередь?

Потому что принцип «первым пришел — первым ушел» сохраняет вершины в порядке их обнаружения, то есть в порядке расстояния. Со стеком вместо очереди поиск сначала уходил бы вглубь: это поиск в глубину.

Может ли BFS находить кратчайшие пути во взвешенных графах?

В общем случае нет: он считает ребра, а не их длины. Для взвешенных графов без отрицательных ребер используйте алгоритм Дейкстры. Если каждый вес равен 0 или 1, подходит вариант под названием 0-1 BFS.

Где применяется BFS?

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

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать поиск в ширину