Поиск в ширину (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 году применил его для трассировки проводников на печатных платах. Сегодня он находит наименьшее число ходов в головоломках, степени разделения в социальных сетях, страницы, до которых веб-краулер доходит первыми, и ближайшую свободную клетку в играх. Когда у ребер есть длины, его обобщает алгоритм Дейкстры.
Попробуйте сами
Откройте приложение и нажмите Шаг. Вершина, которую сейчас посещают, выделена, вершины, ждущие в очереди, синие, а посещенные — зеленые, и на каждой указано расстояние. Очередь показана под графом, начало — первым. Переключите щелчок на Цель и выберите вершину, чтобы остановиться на ней и увидеть кратчайший путь, или создайте новый граф с большим числом вершин и ребер.
Часто задаваемые вопросы
Какова временная сложность BFS?
O(V + E) для V вершин (vertices) и E ребер (edges): каждая вершина один раз попадает в очередь и один раз покидает ее, а каждое ребро проверяется с обоих концов. Нужно O(V) дополнительной памяти на очередь и расстояния.
Почему BFS использует очередь?
Потому что принцип «первым пришел — первым ушел» сохраняет вершины в порядке их обнаружения, то есть в порядке расстояния. Со стеком вместо очереди поиск сначала уходил бы вглубь: это поиск в глубину.
Может ли BFS находить кратчайшие пути во взвешенных графах?
В общем случае нет: он считает ребра, а не их длины. Для взвешенных графов без отрицательных ребер используйте алгоритм Дейкстры. Если каждый вес равен 0 или 1, подходит вариант под названием 0-1 BFS.
Где применяется BFS?
Для решения головоломок и лабиринтов за наименьшее число ходов, поиска друзей друзей в социальных сетях, обхода веба уровень за уровнем, широковещательной рассылки в сетях и как составная часть других алгоритмов, например поиска максимального потока.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать поиск в ширину