Свойства лесов DFS

Как уже говорилось в разделе 18.2, деревья, которые описывают рекурсивную струк­туру вызовов функции DFS, дают ключ для понимания того, как выполняется поиск в глу­бину. В данном разделе мы будем изучать свойства этого алгоритма на примере исследо­вания свойств деревьев DFS.

Если добавить дополнительные узлы в дерево DFS для фиксации моментов, когда мы пропускаем рекурсивные вызовы для уже посещенных вершин, то мы получим компак­тное представление о динамике поиска в глубину, иллюстрацией которой может служить рис. 18.9. Это представление заслуживает подробного изучения. Дерево такого типа яв­ляется представлением графа, при этом каждой вершине дерева соответствует вершина графа, а каждому ребру — ребро графа. Можно выбрать два представления ребра, кото­рое подвергается обработке (по одному в каждом направлении), как показано в левой части рис. 18.9, или только одно представление, как показано в центральной и правой частях рисунка. Первое из них полезно для понимания того факта, что рассматриваемый алгоритм обрабатывает любое и каждое ребро, второе же полезно для понимания, что де­рево DFS есть ни что иное, как еще одно представление графа. Обход внутренних узлов дерева в прямом порядке располагает вершины в последовательности, в которой поиск в глубину их обходит; более того, порядок, в котором происходит посещение ребер де­ревьев при обходе дерева в прямом порядке, совпадает с порядком, в котором поиск в глубину осуществляет просмотр ребер в графе.

В самом деле, дерево DFS, показанное на рис. 18.9, содержит ту же информацию, что и трассировка на рис. 18.5 или пошаговая иллюстрация обхода Тремо на рис. 18.2 и 18.3. Ребра, ведущие ко внутренним узлам, представляют собой ребра (коридоры), ведущие к непосещенным вершинам (перекресткам), а заштрихованные узлы представляют собой ребра, ведущие к вершинам, для которых в данный момент выполняется рекурсивный поиск в глубину (в момент, когда мы открываем дверь в коридор, в котором дверь на противоположном конце уже открыта). В условиях такой интерпретации прямой обход дерева говорит нам то же, что и подробный сценарий обхода лабиринта.

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

■ ребра, представляющие рекурсивные вызовы {древесные ребра - tree edges);

■ ребра, соединяющие конкретную вершину с ее предшественником в дереве DFS,
который не является ее родителем {обратные ребра - back edges)).

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

РИСУНОК 18.9. РАЗЛИЧНЫЕ ПРЕДСТАВЛЕНИЯ ДЕРЕВА DFS

Если расширить дерево рекурсивных вызовов поиска в глубину таким образом, чтобы в него были включены ребра, которые мы проверяем, но не проходим, то получим полное описание процесса поиска в глубину (слева). У каждого узла дерева имеется потомок, представляющий каждый смежный с ним узел в том порядке, в каком они рассматривались алгоритмом DFS, а обход в прямом порядке дает ту же информацию, что и рис. 18.5: сначала мы проходим путь 0-0, затем 0-2, далее мы пропускаем 2-0, затем мы проходим по 2-6, пропускаем 6-2, затем проходим по 6-4, 4-3 и так далее. Вектор ord определяет последовательность, в которой мы посещаем вершины дерева во время обхода в прямом порядке и который аналогичен последовательности посещения вершин графа алгоритмом DFS. Вектор st является представлением в виде родительских связей дерева рекурсивных вызовов поиска в глубину (см. рис. 18.6).

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

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

Поскольку существуют два представления каждого ребра графа, и каждое ребро со­ответствует связи в дереве DFS, разделим связи дерева на четыре класса, воспользовав­шись номерами предпорядка (preorder number) и родительскими связями (соответственно, в массивах ord и st), которые вычисляет наша программа поиска в глубину. Мы рассмат­риваем связь между вершинами v и w в дереве DFS, которая представляет ребро дерева, как

■ древесная связь {tree link), если v не помечена;

■ родительская связь (parent link), если st[w] есть v,

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

назад дает нам новую информацию о структуре графа.

Данные выше определения предоставляют достаточную информацию, чтобы провести различие между связью древовидной структу­ры, родительской связью, связью назад и свя­зью вниз в реализации класса DFS. Обратите внимание на то обстоятельство, что для роди­тельских связей и связей назад выполняется ус­ловие ord[w] < ord[v], т.е., чтобы знать, что v-w представляет собой связь назад, мы должны так­же знать, что st[w] не есть v. На рис. 18.10 пред­ставлена распечатка результатов классификации связей древесной структуры DFS для каждого ребра графа по мере того, как эти ребра встре­чаются в рассматриваемом примере процесса поиска в глубину. Это еще одно полное пред­ставление базового процесса поиска, которое может служить промежуточным этапом между рисунками 18.5 и 18.9.

Четыре описанных выше типа связей в дре­весных структурах соответствуют четырем раз­личным видам трактовки ребер в процессе вы­полнения поиска в глубину; об этом шла речь (в терминах обхода лабиринта) в конце раздела 18.1. Древесная связь соответствует случаю, ког­да поиск в глубину сталкивается с первыми дву­мя представлениями ребра дерева, что приводит к очередному рекурсивному вызову (для иссле­дования еще не просмотренных вершин); роди-

РИСУНОК 18.10. ТРАССИРОВКА ПОИСКА В ГЛУБИНУ (КЛАССИФИКАЦИЯ СВЯЗЕЙ В ДРЕВЕСНЫХ СТРУКТУРАХ)

Данный вариант рис. 18.5 отображает классификацию связей в дереве DFS, соответствующую представлению каждого ребра графа. Древесные ребра (которые соответствуют рекурсивным вызовам) представлены как древесные связи (такими их видит поиск в глубину при первой встрече с ними) и как родительские связи (такими их видит поиск в глубину при второй встрече). Обратные ребра суть связи назад при первой встрече с ними и связи вниз при второй встрече.

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

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

РИСУНОК 18.11. ЛЕС DFS

Лес DFS, изображенный в верхней части рисунка, служит иллюстрацией поиска в глубину на графе, представленном в виде матрицы связности и показанном в нижней правой части диаграммы. Рассматриваемый граф состоит из трех связных компонент, в соответствии с этим фактом лес содержит три дерева. Вектор ort представляет прямой порядок нумерации узлов в дереве (порядок, в котором они подвергаются исследованию со стороны DFS), а вектор st есть представление леса в виде родительских связей. Вектор сс связывает каждую компоненту с индексом связной компоненты (см. программу 18.4). Как и в случае рис. 18.9, ребра, ведущие к кружками, — это древесные ребра, а ребра, ведущие к квадратикам, - обратные ребра; заштрихованные узлы показывают, что инцидент­ное ребро было обнаружено раньше, когда поиск проводился в обратном направлении.

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

Особенности структуры конкретного леса позволяют понять, как ведет себя DFS на том или ином графе, но большая часть свойств DFS, которые представляют для нас ин­терес, зависят от свойств графа, которые, в свою очередь, не зависят от структуры леса. Например, оба леса, показанные на рис. 18.11 и 18.12, содержат три дерева (как и лю­бой другой лес DFS одного и того же графа), поскольку они всего лишь различные пред­ставления одного и того же графа, состоящего из трех связных компонент. В самом деле, прямое следствие основного доказательства того, что поиск в глубину посещает все узлы и ребра конкретного графа (см. свойства 18.2-18.4), заключается в том, что число связ­ных компонент графа равно числу деревьев в лесе DFS. Этот пример служит иллюстра­цией положения, используемого в качестве основы для поиска на графе на протяжении этой книги: разнообразие реализаций классов обработки графов основано на изучении свойств графа путем обработки конкретного его представления (лес, соответствующий поиску).

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

РИСУНОК 18.12. ДРУГОЙ ЛЕС DFS

Данный лес описывает поиск в глубину на том же графе, что и изображенный на рис. 18.11, но в этом случае используется представление графа в виде списков смежных вершин, в силу чего меняется порядок поиска, поскольку в рассматриваемом случае он определяется порядком, в котором узлы появляются в списках смежных вершин. В самом деле, лес сам подсказывает нам этот порядок: это порядок, в каком перечисляются потомки в каждом узле дерева. Например, узлы в списке смежных вершин для вершины 0 расположены в порядке 5216, узлы в списке смежных вершин для вершины 4 — в порядке 6 5 3 и т.д. Как и раньше, все вершины и ребра графа просматриваются во время поиска способом, который был точно описан с помощью обхода дерева в прямом порядке. Векторы ord и st зависят от представления графа и динамики поиска, вследствие чего они отличаются от приводимых на рис. 18.11, в то же время вектор сс зависит только от свойств графа, благодаря чему остается неизменным.

В принципе, можно проводить анализ древесных структур DFS, имея перед собой цель повысить производительности алгоритма. Например, нужно ли предпринимать попытки повысить быстродействие алгоритма путем переделки списков смежных вершин перед началом поиска? Для многих важных классов алгоритмов, использующих поиск в глуби­ну, ответ на этот вопрос отрицательный, поскольку они оптимальны — время их выпол­нения в худшем случае не зависит ни от структуры графа, ни от последовательности, в какой ребра появляются в списках смежных вершин (по существу, они проводят обра­ботку каждого ребра в точности один раз). Тем не менее, леса DFS обладают характер­ной структурой, которая заслуживает изучения уже за то, что она отличает их от другой фундаментальной схемы, которая будет рассматриваться далее в этой главе.

На рис. 18.13 показано дерево DFS графа больших размеров, которое служит иллюс­трацией базовых характеристик динамики поиска в глубину. Это дерево высокое и тон­кое, оно демонстрирует несколько свойств просматриваемого графа и процесса поиска в глубину.

■ Существует, по меньшей мере, один длинный путь, который соединяет существен­
ную часть узлов.

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

■ Мы редко делаем более одного рекурсивного вызова с одного узла.

■ Глубина рекурсии пропорциональна числу вершин графа.