Анатомия поиска DFS в орграфах

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

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

Подобно тому, как мы поступали в главе 18, воспользуемся двумя терминами. Термин стандартный поиск в глубину на списках смежных вершин (standard adjacency-lists DFS) будет обозначать процесс вставки последовательности ребер в АТД орграфа, представленного в виде списков смежных вершин (конструктор из программы 17.9, при вызове которого во втором аргументе передается значение true), с последующим выполнением поиска в глубину, например, с помощью программы 18.3. Второй, и аналогичный, термин стандар­тный поиск в глубину на матрице смежности (standard adjacency-matrix DFS) будет обозна-

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

чать процесс вставки некоторой последователь­ности ребер в АТД орграфа, представленного в виде матрицы смежности (конструктор из про­граммы 17.7, при вызове которого во втором аргументе передается значение true), с последу­ющим выполнением поиска в глубину, напри­мер, с помощью программы 18.3.

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

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

■ Класс ребер, представляющих рекурсив­
ный вызов (древесные (tree) ребра).

■ Класс ребер, ведущих из той или иной
вершины к ее предшественнику в дереве
поиска в глубину (обратные (back) ребра).

■ Класс ребер, ведущих из вершины к по­
томку в его дереве поиска в глубину
(прямые (down) ребра).

РИСУНОК 19.9. ЛЕС DFS ДЛЯ ОРГРАФОВ

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