Глава 18. Поиск на графе. Этот рисунок прослеживает процесс поиска в ширину на заданном примере

РИСУНОК 1821. ПОИСК В ШИРИНУ

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

Часть 5. Алгоритмы на графах

Как мы могли убедиться в разделе 18.4, поиск в глубину подобен исследованию лабиринта, проводи­мого одним человеком. Поиск в ширину можно срав­нить с исследованием, проводимым группой людей, рассыпавшихся веером по всем направлениям. Не­смотря на то что поиски в глубину и в ширину отли­чаются друг от друга во многих аспектах, здесь умес­тно подчеркнуть то, что между этими двумя методами существует прочная глубинная связь — такая, какую мы обнаружили, когда проводили краткий анализ ме­тодов в главе 5. В разделе 18.8 мы рассмотрим обоб­щенный метод поиска на графе, который мы можем переделать таким образом, чтобы он включал в себя оба эти алгоритма, равно как и множество других. Каждый алгоритм обладает собственными динамичес­кими характеристиками, которые мы используем для решения соответствующих задач обработки графов. Что касается поиска в ширину, то наибольший инте­рес для нас представляет расстояние каждой вершины от исходной вершины (длина кратчайшего пути, со­единяющего две эти вершины).

Свойство 18.9. В процессе поиска в ширину вершины поступают в очередь FIFO и покидают ее в порядке, определяемом их расстоянием от исходной вершины.

Доказательство: Справедливо более сильное условие: очередь всегда содержит ноль или большее число вершин, удаленных на к из исходной точки, за кото­рой следует ноль или большее число вершин, уда­ленных на к + 1 от исходной точки, где к - некото­рое целое значение. Это более сильное условие легко доказывается методом индукции. ■

Что касается поиска в глубину, то понимание ди­намических характеристик этого алгоритма достигает­ся с помощью леса поиска DFS, который описывает структуру рекурсивных вызовов алгоритма. Основное свойство упомянутого леса состоит в том, что он пред­ставляет пути из каждой вершины в точку, откуда на­чался поиск связной компоненты, в которой она на­ходится. Как показывает реализация и рис. 18.22, такое остовное дерево помогает достичь понимания поиска в ширину. Как и в случае поиска в глубину, мы имеем лес, который характеризует динамику по­иска, по одному дереву на каждую связную компо­ненту, один узел дерева приходится на каждую верши-

РИСУНОК 18.22. ДЕРЕВО BFS

Это дерево представляет собой компактное описание динамических характеристик поиска в глубину в стиле, свойственном дереву, которое показано на рис. 18.9. Обход дерева в порядке уровней показывает нам, как разворачивается поиск: сначала мы наносим визит вершине 0, потом мы посещаем вершины 2, 5 и 7, затем, находясь в 2, мы выясняем, что в вершине 0 мы уже были, и направляемся в 6 и т.д. У каждого узла дерева имеются потомки, и каждый из них представляет узлы, смежные с этим узлом, в том порядке, в каком они рассматрива­ются алгоритмом BFS. Как и на рис. 18.9, связи дерева BFS соответству­ют ребрам графа: если мы заменим ребра, ведущие во внешние узлы, на линии, ведущие в заданный узел, то мы получим чертеж графа. Связи, ведущие во внешние узлы, представ­ляют собой ребра, которые не были помещены в очередь, так как они направлены в помеченные узлы: это либо родительские связи, либо перекрестные связи, которые указывают на некоторый узел, находящийся на том же уровне или на уровне, более близком к корню дерева.

Вектор st есть представление дерева в виде родительских связей, которое мы можем использовать при поиске кратчайшего пути из любого узла в корень. Например, 3-5-0 представляет собой путь в графе из 3 в 0, поскольку st[3] есть 5, а st[5] - 0. Никакой другой путь из З в 0 не может быть короче.