Глава 18. Поиск на графе. являются шаблонами многочисленных алгоритмов, обладающих этим свойством

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

Кратчайший путь. Найти кратчайший путь на графе, ведущий из v в w. Мы можем ре­шить эту задачу, инициируя процесс поиска в ширину, который поддерживает в верши­не v представление st дерева поиска в виде родительских связей, прекращая этот процесс по достижении вершины w. Путь из w в v вверх по дереву и является самым коротким. Например, после построения объекта bfs класса BFS< Graph> может использовать сле­дующий программный код для распечатки пути, ведущего из w в v:

for (t = w; t! =w; t = bfs.ST(t)) cout «t «" -"; cout «v «endl;

Чтобы получить путь v в w, замените в этом узле операцию cout на операцию затал­кивания индексов в стек, затем войдите в цикл, который распечатывает индексы этих вер­шин после выталкивания их из стека. Либо начните поиск в w и остановите его тогда, когда v окажется на первом месте.

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

Кратчайшие пути для всех пар вершин. Найти кратчайший путь, соединяющий каж­дую пару вершин графа. Способ решения этой задачи предусматривает использование класса BFS, который решает задачу единственного источника для каждой вершины фа-фа и поддерживает функции-элементы, которые способны эффективно выполнить обра­ботку громадного числа запросов на вычисление кратчайших путей за счет сохранения представлений длин путей и дерева родительских связей для каждой вершины (см. рис. 18.23). Такая предварительная обработка требует времени, пропорционального VE, и про­странства памяти, пропорционального V², что делает невозможной обработку крупных разреженных графов. Тем не менее, она позволяет строить АТД с оптимальными рабо­чими характеристиками: после определенных затрат ресурсов на предварительную обра­ботку (и пространства памяти для сохранения результатов такой обработки), можно вы­числить длины кратчайших путей за постоянное время, а сами пути - за время, пропорциональное их длине (см. упражнение 18.55).

Такие решения, полученные благодаря применению поиска в ширину, достаточно эффективны, однако здесь мы не будем рассматривать дополнительные подробности, по­скольку они представляют собой специальные случаи алгоритмов, которые будут иссле­доваться в главе 21. Понятие кратчайшего пути (shortest path) в графе в общем случае ис­пользуется для описания соответствующих задач в орграфах и сетях.

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

РИСУНОК 18.23. ПРИМЕР ПОИСКА КРАТЧАЙШИХ ПУТЕЙ ДЛЯ ВСЕХ ПАР ВЕРШИН

Изображенные на данном рисунке диаграммы описывают результат выполнения поиска в ширину из каждой вершины, благодаря чему производится вычисление кратчайших путей, соединяющих все пары вершин. Каждый поиск приводит к построению дерева BFS, которое определяет кратчай­шие пути, соединяющие все вершины графа с вершиной в корне дерева. Результаты всех выполненных поисков сводятся в две матрицы, показанные в нижней части рисунка. В левой матрице элемент на пересечении строки v и столбца v представляет длину кратчайшего пути из v в w (глубина v в дереве w). Каждая строка правой матрицы содержит массив st для соответствующего поиска. В условиях рассматриваемого примера кратчайший путь из 3 в 2 состоит из трех ребер, как показывает элемент левой матрицы, расположенный на пересечении строки 3 и столбца 2. Третье сверху слева дерево BFS говорит нам, что таким путем является 3-4-6-2, и эта информация закодирована в строке 2 матрицы справа. Матрица не обязательно должна быть симметричной, когда суще­ствуют несколько кратчайших путей, поскольку обнаружен­ные пути зависят от порядка выполнения поиска в ширину. Например, дерево BFS, пока­занное внизу слева, и строка 3 правой матрицы говорят нам, что кратчайшим путем из 2 в 3 является 2-0-5-3.

Глава 18. Поиск на графе

Этой теме посвящена глава 21. Решения, которые там изучаются, являются строгими обобщениями описанных здесь решений с применением поиска в ширину.

Базовые характеристики динамики поиска резко контрастируют с аналогичными ха­рактеристиками поиска в глубину, что и демонстрирует большой граф, изображенный на рис. 18.24, если его сравнить с рис. 18.13. Дерево имеет небольшую глубину, зато обла­дает протяженной шириной. Оно может служить иллюстрацией множества особенностей, которыми поиск в ширину на графе отличается от поиска в глубину. Например:

■ Существует относительно короткий путь, соединяющий каждую пару вершин
графа.

■ Во время поиска большая часть вершин будет смежными со множеством непосе­
щенных вершин.

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

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

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

Данный рисунок служит иллюстрацией того, что поиск в ширину протекает в случайном эвклидовом графе с близкими связями (слева) в том же стиле, что и показанный на рис. 18.13. Как легко видеть из этого примера, дереву BFS свойственна малая глубина и большая ширина на рассматриваемом типе графа (а также для многих других типов графов, которые часто встречаются на практике). Иначе говоря, в рассматриваемом случае вершины соединены между собой, в основном, короткими путями. Различие между формами деревьев DFS и BFS свидетельствуют о существенном различии динамических характеристик этих алгоритмов.