Поиск в ширину

Предположим, что мы хотим найти кратчайший путь (shortest path) между двумя конк­ретными вершинами некоторого графа - путь, соединяющий вершины, обладающие тем свойством, что никакой другой путь, соединяющий эти вершины, не содержит меньшее число ребер. Классический метод решения этой задачи, получивший название поиска в ширину (BFS — breath-first search), служит основой многочисленных алгоритмов обработки графов; именно он и будет изучаться в данном разделе. Поиск в глубину мало пригоден для решения этой задачи, поскольку предлагаемый им порядок прохождения графа не имеет отношения к поиску кратчайших путей. В отличие от поиска в глубину, поиск в ширину предназначен как раз для достижения этой цели. Поиск кратчайшего пути от вер­шины v к вершине w мы начнем с того, что среди всех вершин, в которые можно перейти по одному ребру из вершины v, мы попытаемся обнаружить вершину w, затем мы про­веряем все вершины, в которые мы можем перейти по двум ребрам, и т.д.

Когда во время просмотра графа мы попадаем в такую точку, из которой исходят более одного ребра, мы выбираем одно из них и запоминаем остальные для дальнейшего про­смотра. В поиске в глубину для этой цели мы используем стек магазинного типа (кото­рым управляет система, благодаря чему обеспечивается поддержка рекурсивной функции поиска). Применение правила LIFO (Last In First Out — последним пришел, первым об­служен), которое характеризует работу стека магазинного типа, соответствует исследова­нию соседних коридоров в лабиринте: из всех еще не исследованных коридоров выби­рается последний из тех, с которым мы столкнулись. В поиске в ширину мы хотим проводить исследование вершин в зависимости от их удаления от исходной точки. В слу­чае реального лабиринта для проведения исследований в таком порядке может потребо­ваться специальная команда исследователей; однако в компьютерной программе эта цель достигается намного проще: мы просто вместо стека используем очередь FIFO (FIFO queue - первым пришел, первым обслужен).

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

■ Выбираем ребра из очереди до тех пор, пока не найдем такое ребро, которое ве­
дет на непосещенную вершину.

■ Просматриваем эту вершину; ставим в очередь все ребра, исходящие из этой вер­
шины в вершины, которые мы еще не посещали.

Рисунок 18.21 иллюстрирует последовательный процесс поиска в ширину (BFS) на конкретном примере.

Ребро 7-4 показано серым цветом, поскольку мы могли бы и не устанавливать его в очередь, так как имеется еще одно ребро, которое ведет в вершину 4, уже помещенную в очередь. В завершение поиска мы удаляем оставшиеся ребра из очереди, полностью иг­норируя при этом серые ребра, когда они вверху очереди (справа). Ребра поступают в очередь и покидают ее в порядке их удаленности от вершины 0.