М.А. Басараб, А.Б. Домрачева, В.М. Купляков
4
ляться вершины. Помимо этого, чтобы иметь возможность восстано-
вить пройденный путь, понадобится массив «предков», где будет
указано, из какой вершины ведет путь в данную. Необходим также
номер стартовой вершины
s
(координаты стартовой ячейки). Сам ал-
горитм можно понимать как процесс «поджигания» графа: на нуле-
вом шаге «поджигаем» только вершину
s
. На каждом следующем ша-
ге «огонь» с уже «горящей» вершины перекидывается на всех ее
соседей. Таким образом, за одну итерацию алгоритма происходит
расширение «кольца огня» в ширину на единицу (отсюда и название
алгоритма).
Более строго это можно представить следующим образом. Созда-
дим очередь, в которую будут помещаться «горящие» вершины,
а также заведем булевский массив, в котором для каждой вершины
будем отмечать, «горит» она или нет (иными словами, была ли она
посещена). Изначально в очередь помещается только вершина
s
. За-
тем реализуется цикл: пока очередь не пуста, достать из ее головы
одну вершину, просмотреть все ребра, исходящие из этой вершины,
и, если какие-то из просмотренных вершин еще не «горят», «под-
жечь» их и поместить в конец очереди.
В итоге, когда очередь опустеет, алгоритм BFS обойдет все дости-
жимые из
s
вершины, причем до каждой дойдет кратчайшим путем.
Также можно посчитать длины кратчайших путей (для чего просто надо
завести массив длин путей) и компактно сохранить информацию, доста-
точную для восстановления всех этих кратчайших путей (завести мас-
сив «предков», в котором для каждой вершины необходимо хранить
номер вершины, из которой мы в нее попали).
При достижении конечной вершины алгоритм прекращает свою
работу и восстанавливается общий путь до конечной вершины.
Одна из возможных оптимизаций алгоритма BFS заключается в
добавлении поиска направленности движения. Зачастую путь меж-
ду двумя вершинами оказывается заключенным в соответствую-
щий прямой угол, поэтому добавлять вершину в очередь можно, не
обходя последовательно все соседние с ней, а начиная от биссек-
трисы соответствующего прямого угла и расходясь в стороны, при
этом беря поочередно вершины с каждой из сторон по отношению
к биссектрисе.
Другая возможность оптимизации — двунаправленный поиск
в ширину. Это улучшает простой поиск BFS
тем, что запускаются
два одновременных поиска в ширину из стартового и конечного
узлов, и процесс останавливается, когда узел из одного фронта по-
иска находит соседний узел из другого фронта. Это может улуч-
шить простой поиск в ширину (обычно в 2 раза), который остается
при этом не очень эффективным.
