Чтобы построить остовный лес, начнем с узла Vi. ПОИСК (wi) вызывает ПОИСК (Уа), а тот вызывает ПОИСК (уз). Последний вызов ничего не добавляет к дереву, ибо единственное ребро с началом Vs идет в узел Vi, уже помеченный как "старый". Поэтому возвращаемся к ПОИСК (Уа), который добавляет Vt в качестве второго сына узла Уа- ПОИСК (У4) заканчивает работу, ничего не добавляя к лесу, поскольку узел Vs уже "старый". Затем заканчивается ПОИСК (Уа). ибо все ребра, выходящие из Уа, к данному моменту просмотрены. Поэтому возвращаемся обратно в Vi и вызываем ПОИСК (Уа)- Последний вызов ничего не добавляет к дереву; аналогично ничего не может добавить и ПОИСК (yj.

Теперь возьмем Уб в качестве корня нового глубинного остовного дерева. Его построение аналогично предыдущему, и мы оставляем его читателю. Заметим, что узлы посещались в порядке Vl, Уа, . . ., Vg. Следовательно, в процессе поиска в глубину узлу vt был приписан номер i, li8. □

При поиске в глубину на ориентированном графе в дополнение к древесным ребрам возникает еще три типа ребер. Это обратные ребра, такие, как (Уз, Vi) на рис. 5.13,6, поперечные справа налево, такие, как (У4, Уз) на том же рисунке, и прямые ребра, такие, как (Уь У4). Однако никакое ребро не идет из узла с меньшим номером, присвоенным в процессе поиска в глубину, в ребро с большим номером, если только последнее не является потомком первого. Это не случайно.

Объяснение аналогично объяснению того, почему в неориентированном случае нет поперечных ребер. Пусть (у, w) - ребро и узел у был посещен до w (т. е. у<ш). Каждый узел, которому приписывается номер в период между началом и концом процедуры ПОИСК (у), становится потомком узла у. Но узел w должен получить свой номер, когда рассматривается ребро (у, w), если только он уже не получил номер раньше. Если w получает номер в то время, когда рассматривается ребро (у, w), то (у, w) становится древесным ребром, а в противном случае прямым ребром. Таким образом, не может быть такого поперечного ребра (у, w), что v<.w.

Поиск в глубину в графе G разбивает множество его ребер на четыре класса.

1) Древесные ребра, идущие к новым узлам в процессе поиска.

2) Прямые ребра, идущие от предков к подлинным потомкам, но не являющиеся древесными ребрами.

3) Обратные ребра, идущие от потомков к предкам (возможно, из узла в себя).

4) Поперечные ребра, соединяющие узлы, которые не являются ни предками, ни потомками друг друга.

Ключевое свойство поперечных ребер устанавливается в следующей лемме.

Лемма 5.6. Если (и, w) - поперечное ребро, то v-w, т. е. поперечные ребра идут справа налево.

Доказательств о. Доказательство аналогично доказательству леммы 5.3 и остается в качестве упражнения. □

5.5. СИЛЬНАЯ СВЯЗНОСТЬ

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

Определение. Пусть G= (V, Е) - ориентированный граф. Разобьем множество его вершин V на такие классы эквивалентности Vh что узлы V и W эквивалентны тогда и только тогда,

когда на графе есть пути из у в ш и обратно. Пусть Е,, -

множество ребер, соединяющих пары узлов в Vi. Графы Gi=(Vi, Ei) называются сильно связными компонентами графа G. Хотя каждый узел графа G принадлежит некоторому множеству Уг, у графа G могут быть ребра, не принадлежащие ни одному множеству Граф называется сильно связным, если он имеет только одну сильно связную компоненту.

Применим поиск в глубину для нахождения сильно связных компонент графа. Сначала покажем, что узлы каждой сильно связной компоненты образуют связный подграф в глубинном остовном лесу. Этот связный подграф представляет собой дерево, и его корень называется корнем сильно связной компоненты. Однако не каждое дерево в глубинном остовном лесу непременно представляет какую-то сильно связную компоненту.

Лемма 5.7. Пусть Gi= (Vi, Ei) - сильно связная компонента, ориентированного графа G, а S= (У, Т) - глубинный остовный лес для G. Тогда узлы графа Gi вместе с ребрами, входящими в пересечение Ei П 7", образуют дерево.

Доказательство. Пусть у и ау - узлы из Vi. (Мы предполагаем, что именами узлов являются номера, присвоенные им в процессе поиска в глубину.) Без потери общности будем считать, что у<ш. Так как узлы у и ш оба принадлежат одной и той же сильно связной компоненте, то существует путь Р в Gi, идущий из V в W. Пусть X - узел на Я с наименьшим номером (возможно, это сам узел у). Путь Р, дойдя до какого-нибудь потомка узла х, уже не сможет выйти за пределы поддерева потомков узла х, ибо за пределы этого поддерева выходят лишь поперечные ребра и обратные ребра, идущие в узлы с номерами, меньшими х. (Так

как потомки узла х занумерованы последовательно, начиная с х, то поперечное или обратное ребро, выходящее из поддерева потомков узла X, должно идти в узел с номером, меньшим х.) Следовательно, W - потомок узла х. Поскольку узлы занумерованы в прямом порядке, то все узлы, номера которых заключены между хяш, также являются потомками узла х. Так как а;у<ш, то у - потомок узла X.

Мы только что показали, что любые два узла в G; имеют общего предка в G;. Пусть т - общий предок узлов графа G, с наименьшим номером. Если v - узел графа Gu то любой узел на пути из r в у, проходящем в остовном дереве, также является узлом графа G,. □

Сильно связные компоненты ориентированного графа G можно найти, построив корни компонент в том порядке, в каком они встретились в последний раз в процессе поиска в глубину на G. Пусть Ti, Га, . . ., - эти корни В ТОМ порядке, в каком заканчивался их поиск в глубину (т. е. поиск узла заканчивался перед поиском /"j+i). Тогда для каждого /</ либо лежит слева от Tj, либо fi - потомок узла tj в глубинном остовном лесу.

Пусть Gj - сильно связная компонента с корнем Tj, lt. Тогда Gi состоит из всех потомков узла г, поскольку никакой узел Г), />1, не может быть потомком узла Гх. Аналогично можно доказать следующую лемму.

Лемма 5.8. Для любого i, \ik, граф Gi состоит из узлов, являющихся потомками узла ri и не принадлежащих ни одному из графов Gi, Ga, . . ., Gj i.

Доказательство. Корень Г} для />1 не может быть потомком узла /-j, поскольку вызов процедуры ПОИСК (о) завершается после работы процедуры ПОИСК (/"j). □

Для нахождения корней введем функцию, называемую НИЖ-НЯЯСВЯЗЬ:

НИЖНЯЯСВЯЗЬ [и] = МШ {{v} и {w I есть поперечное или

обратное ребро из некоторого потомка узла у в узел w, а корень той сильно связной компоненты, которая содержит W, является предком узла у}). (5.3)

На рис. 5.14 изображено поперечное ребро из потомка узла у в узел W, а корень г сильно связной компоненты, содержащей w, является предком узла у.

Мы скоро увидим, как в процессе поиска в глубину вычислять функцию НИЖНЯЯСВЯЗЬ. Но прежде охарактеризуем корни сильно связных компонент в терминах значений этой функции.