Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 131
Текст из файла (страница 131)
Полученные решения затем комбинируются в соответствии со структурой связей между сильно связными компонентами. В приложении Б сказано, что сильно связный компонент ориентированного графа С = (У, Е) представляет собой максимальное множество вершин С С У, такое что для каждой пары вершин и и о из С справедливо как и - е, так и о -» и, т.е. вершины и и о достижимы друг из друга. На рис. 22.9 приведены примеры сильно связных компонентов. Наш алгоритм поиска сильно связных компонентов графа С = (У, Е) использует транспонирование С, которое определяется в упражнении 22.1-3 как граф Ст = (У,Е ), где Е = ((и,е): (п,и) еЕ), т.е. Е состоит из ребер С путем изменения их направления на обратное. Для представления с помощью списков смежности данного графа С получить граф Ст можно за время О (У+ Е). Интересно заметить, что графы С и Ст имеют одни и те же сильно связные компоненты: и и о достижимы друг из друга в С тогда и толью тогда, югда они Часть Ч1.
Алгоритмы для работы с графами 636 а... ь с )ЭВ6936Ю )' [ Рис. 22.9. Сильно связные компоненты ориентированного графа достижимы друг из друга в Ст. На рис. 22.9б показан граф, представляющий собой результат транспонирования графа на рис. 22.9а (сильно связные компоненты выделены штриховкой). Далее приведен алгоритм, который за линейное время б1($'+ Е) находит сильно связные компоненты ориентированного графа С = (Ч Е) благодаря двойному поиску в глубину, одному — в графе С, и второму — в графе СТ.
БткОхОеу СОххесте0 СОмРОхехтз(С) 1 Вызов 13ГБ(С) для вычисления времен завершения 1[и] для каждой вершины и 2 Построение СТ 3 Вызов )ЗРИМ(С~), но в главном цикле процедуры 0ГБ, вершины рассматриваются в порядке убывания значений г"[и] вычисленных в строке 1 4 Деревья леса поиска в глубину, полученного в строке 3 представляют собой сильно связные компоненты Идея, лежащая в основе этого алгоритма, опирается на ключевое свойство графа компонентов (сошропеп1 ятарЬ) Се~~ = (Ъ'е~~, Ез~~), который определяется Глава 22. Элементарные алгоритмы для работы с графами 637 следующим образом. Предположим, что С имеет сильно связные компоненты Сы Сз,..., Ся. Множество вершин Ъ'~~~ = (оы пз,..., оь) состоит из вершин и, для каждого сильно связного компонента С; графа С. Если в С имеется ребро (х, у) для некоторых двух вершин х е С; и у е Су, то в графе компонент имеется ребро (о;, и ) е ЕаОО.
другими словами, если сжать все ребра между смежными вершинами в каждом сильно связном компоненте графа С, мы получим граф С~~~ (вершинами которого являются сильно связные компоненты графа С). На рис. 22.9в показан граф компонентов для графа, приведенного на рис. 22,9а. Ключевое свойство графа компонентов заключается в том, что он представляет собой ориентированный ациклический граф, как следует из приведенной ниже леммы. Лемма 22.13. Пусть С и С' — различные сильно связные компоненты в ориентированном графе С = (Ъ; Е), и пусть и, о е С и и',о' е С', а кроме того, предположим, что в С имеется путь и - и'. В таком случае в С не может быть пути и > и. Доказательсгиво. Если в С имеется путь о' - и, то в С имеются и пути пи' - и' и и' - п - и.
Следовательно, вершины и и и' достижимы одна из другой, что противоречит предположению о том, что С и С' — различные сильно связные компоненты, Мы увидим, что при рассмотрении вершин в процессе второго поиска в глубину в порядке убывания времен завершения работы с вершинами, которые были вычислены при первом поиске в глубину, мы по сути посещаем вершины графа компонентов (каждая из которых соответствует сильно связному компоненту С) в порядке топологической сортировки. Поскольку процедура ЯТКОМОЬТ СОИХЕСТЕО СОМРОИЕХТБ выполняет два поиска в глубину, имеется потенциальная неоднозначность при рассмотрении значений И ~и) и г" (и].
В этом разделе данные значения будут относиться исключительно к времени открытия и времени завершения, вычисленным при первом вызове процедуры РРБ в строке 1. Мы распространим обозначения для времени открытия и времени завершения на множества вершин. Если У С У, то мы определим о(У) = ппп„вп (Н~и)) и г" (У) = шах„еп(г" Щ, т.е. Н(У) и г'(У) представляют собой самое раннее время открытия и самое позднее время завершения для всех вершин в У. Следующая лемма и следствие из нее описывают ключевое свойство, связывающее сильно связные компоненты и времена завершения, полученные при первом поиске в глубину. Часть Ч].
Алгоритмы для работы с графами 638 Лемма 22.14. Пусть С и С' — различные сильно связные компоненты в ориентированном графе С = (К Е). Предположим, что имеется ребро (и, и) Е Е, где и Е С и и Е С'. Тогда г' (С) > г (С'). Доказательства. Имеется два возможных случая в зависимости от того, какой вз сильно связных компонентов, С или С', содержит первую открытую в процессе поиска в глубину вершину.
Если Н(С) < Н(С'), то обозначим первую открытую в С вершину как х. В момент времени Н [х] все вершины в С и С' — белые. В С имеется путь от х к каждой вершине в С, состоящий только из белых вершин. Поскольку (и, и) е Е, для любой вершины и~ Е С' в момент времени Н [х] в графе С имеется также путь от х к и, состоящий только из белых вершин: х - и и -» и. Согласно теореме о белом пути, все вершины в С и С' становятся потомками х в дереве поиска в глубину. Согласно следствию 22.8, г" [х] = )'(С) > 1'(С').
Если же Н (С) > Ы (С'), то обозначим первую открытую вершину в С' как у. В момент Н [у] все вершины в С' белые, и в С имеется путь от у к каждой вершине С', состоящий только из белых вершин. В соответствии с теоремой о белом нуги, все вершины в С' становятся потомками у в дереве поиска в глубину, так что согласно следствию 22.8, 1 [у] = Г (С'). В момент времени с1 [у] все вершины в С белые. Поскольку имеется ребро (и, и) из С в С', из леммы 22.13 вытекает, что не существует пути из С' в С. Следовательно, в С не имеется вершин, достижимых из у.
Таким образом, в момент времени 1 [у] все вершины в С остаются белыми. Значит, для любой вершины и Е С имеем г" [ш] > У [у], откуда следует, что г" (С) > > г" (С'). И Приведенное ниже следствие говорит нам, что каждое ребро в Ст, соединяющее два сильно связных компонента, идет от компонента с более ранним временем завершения (при поиске в глубину) к компоненту с более поздним временем завершения. Следствие 22.15.
Пусп С и С' — различные сильно связные компоненты в ориентированном графе С = (У, Е). Предположим, что имеется ребро (и, и) е Ет, где и Е С и и е С'. Тогда г" (С) < У (С'). Доказательства Поскольку (и, и) Е Е г, (и, и) Е Е. Так как сильно связные компоненты С и Ст одни и те же, из леммы 22.14 следует, что г" (С) < г" (С'). и Следствие 22.15 дает нам ключ к пониманию того, как работает процедура Ятконях Сомннстю Сомромннтз. Рассмотрим, что происходит, когда мы выполняем второй поиск в глубину над графом Ст. Мы начинаем с сильно связного компонента С, время завершения которого г" (С) максимально.
Поиск начинается с некоторой вершины х е С, при этом посещаются все вершины в С. Согласно Глава 22. Элементарные алгоритмы для работы с графами 639 следствию 22.15, в Ст нет ребер от С к другому сильно связному компоненту, так что при поиске из х не посещается ни одна вершина в других компонентах. Следовательно, дерево, корнем которого является х, содержит только вершины из С. После того как будут посещены все вершины в С, поиск в строке 3 выбирает в качестве корня вершину из некоторого другого сильно связного компонента С', время завершения 1 (С') которого максимально среди всех компонентов, исключая С.
Теперь поиск посещает все вершины в С'. Согласно следствию 22.15, в Ст единственным ребром из С' в другие компоненты может быть ребро в С, но обработка компонента С уже завершена. В общем случае, когда поиск в глубину в Ст в строке 3 посещает некоторый сильно связный компонент, все ребра, исходящие из этого компонента, идут в уже обработанные компоненты. Следовательно„ каждый поиск в глубину обрабатывает ровно один сильно связный компонент.
Приведенная далее теорема формализует это доказательство. Теорема 22.16. Процедура Ятиоыои' Со]чместпо Сомроынчтз(С) корректно вычисляет сильно связные компоненты ориентированного графа С. Доказатвльсогво. Воспользуемся индукцией по количеству найденных деревьев при поиске в глубину в Ст в строке 3, и докажем, что вершины каждого дерева образуют сильно связный компонент. Гипотеза индукции состоит в том, что первые й деревьев, полученные в строке 3, являются сильно связными компонентами.
Для случая й = О это утверждение тривиально. Для выполнения шага индукции предположим, что каждое из первых й деревьев поиска в глубину в строке 3, представляет собой сильно связный компонент, и рассмотрим (/с + 1)-е дерево. Пусть корнем этого дерева является вершина и, и пусть и принадлежит сильно связному компоненту С. В соответствии с тем как мы выбираем корни при поиске в глубину в строке 3, для любого сильно связного компонента С', который еще не был посещен и отличен от С, справедливо соотношение Г" ~и] = Г" (С) ) Г" (С').
В соответствии с гипотезой индукции в момент времени, когда поиск посещает вершину и, все остальные вершины С вЂ” белые. Согласно теореме о белом пути, все вершины С, кроме и, являются потомками и в дереве поиска в глубину. Кроме того, в соответствии с гипотезой индукции и со следствием 22.15, все ребра в Ст, которые покидают С, должны идти в уже посещенные сильно связные компоненты. Таким образом, ни в одном сильно связном компоненте, отличном от С, нет вершины, которая бы стала потомком и в процессе поиска в глубину в Ст. Следовательно, вершины дерева поиска в глубину в Ст, корнем которого является и, образуют ровно один сильно связный компонент, что и завершает шаг индукции и доказательство данной теоремы. Вот еще одна точка зрения на работу второго поиска в глубину.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
