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

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

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

Для исходной вершины мы помещаем в очередь фиктивную петлю, после чего выполняем следующие действия до тех пор, пока очередь не опустеет:

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

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

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

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

Этот рисунок прослеживает процесс поиска в ширину на заданном примере. Мы начинаем его на всех ребрах, смежных с исходной вершиной в очереди (диаграмма вверху слева). Далее, мы переносим ребро 0-2 из очереди в дерево и приступаем к обработке инцидентных ему ребер 2-0 и 2-6 (вторая диаграмма сверху слева). Мы не помещаем ребро 2-0 в очередь, поскольку вершина 0 уже содержится в дереве. Затем мы переносим ребро 0-5 из очереди в дерево; и снова ребра, инцидентные вершине 5, не приводят нас к новым вершинам, однако мы добавляем в очередь ребра 5-3 и 5-4 (третья диаграмма сверху слева). После этого мы добавляем ребро 0-7 в дерево и устанавливаем ребро 7-1 в очередь (диаграмма внизу слева).

Как мы могли убедиться в предыдущем разделе, поиск в глубину подобен исследованию лабиринта, проводимого одним человеком. Поиск в ширину можно сравнить с исследованием, проводимым группой людей, рассыпавшихся веером по всем направлениям. Несмотря на то что поиски в глубину и в ширину отличаются друг от друга во многих аспектах, здесь уместно подчеркнуть то, что между этими двумя методами существует прочная глубинная связь.

Рисунок 43

С помощью поиска в ширину мы можем решить задачи обнаружения остовного дерева, связных компонент, поиска вершин и ряд других базовых задач связности, поскольку рассмотренные решения зависят только от способности алгоритма поиска анализировать каждый узел и каждое ребро, связанное с исходной точкой. Поиски в ширину и в глубину являются шаблонами многочисленных алгоритмов, обладающих этим свойством. Как уже отмечалось в начале данного раздела, наш повышенный интерес к поиску в ширину объясняется тем, что он является естественным алгоритмом поиска на графе для приложений, в условиях которых требуется знать кратчайший путь между двумя заданными вершинами. Далее, мы рассмотрим конкретное решение этой задачи.