Изменения
→Псевдокод
==Алгоритм==
#Построить граф <tex>H</tex> с обратными (инвертированными) рёбрами
#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> - — время окончания обработки вершины <tex>u</tex>#Выполнить поиск в глубину в <tex>G</tex>, перебирая вершины во внешнем цикле в порядке убывания <tex>f[u]</tex>
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.<br>
Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - — на <tex>H</tex>.<br clear ="all"> ==Доказательствокорректности алгоритма=={{Теорема|statement=Рассмотрим пару вершин Вершины <tex>s</tex> и <tex>t</tex>взаимно достижимы <tex>\Leftrightarrow</tex> после выполнения алгоритма они принадлежат одному дереву обхода в глубину.|proof=<tex>\Rightarrow</tex> Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимыв графе <tex>G</tex>, то они обязательно будут находиться в одном дереве поиска на третьем этапе будет найден путь из одной вершины в глубинудругую, посколькуэто означает, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корнячто по окончанию алгоритма обе вершины лежат в одном поддереве. <brtex>\Leftarrow</tex>Теперь докажем, что если # Вершины <tex>s</tex> и <tex>t</tex> находятся лежат в одном и том же дереве поискав глубину на третьем этапе алгоритма. Значит, то что они являются сильно связанными. Пусть обе достижимы из корня <tex>r</tex> - корень этого дерева. Тогда существует путь # Вершина <tex>r \rightsquigarrow s</tex>была рассмотрена вторым обходом в глубину раньше, из чего следует, что в инвертированном графе есть путь чем <tex>s \rightsquigarrow r</tex>. Очевидно, что и <tex>f[r]t</tex> > , значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин <tex>f[s]</tex>, т. к. мы рассматриваем вершины в порядке убывания и <tex>f[u]t</tex>. Предположим, что пути Из этого мы получаем 2 случая:##Обе эти вершины были достижимы из <tex>s \rightsquigarrow r</tex> в исходном инвертированном графе нет. Тогда в инвертированном графе нет пути А это означает взаимную достижимость вершин <tex>r \rightsquigarrow s</tex>. Исходя из факта существования в инвертированном графе и <tex>s \rightsquigarrow r</tex> и отсутствия взаимную достижимость вершин <tex>r \rightsquigarrow s</tex>, делаем вывод, что и <tex>rt</tex> была посещена как потомок . А складывая пути мы получаем взаимную достижимость вершин <tex>s</tex> в дереве поиска в глубину или и <tex>t</tex>.##Хотя бы одна не достижима из <tex>r</tex> уже была обработана поиском в глубину на момент начала поиска из инвертированном графе, например <tex>st</tex>. Но тогда Значит и <tex>f[s]r</tex> > была не достижима из <tex>f[r]t</tex>в инвертированном графе, что является противоречием. Значит, наше предположение об отсутсвии пути так как время выхода <tex>s \rightsquigarrow r</tex> было не верно- больше . Тогда в исходном графе существуют Значит между этими вершинами нет пути как , но последнего быть не может, потому что <tex>s \rightsquigarrow rt</tex>, так и была достижима из <tex>r \rightsquigarrow s</tex>по пункту 1). Значит, тиз случая 2.е1 и не существования случая 2. 2 получаем, что вершины <tex>rs</tex> и <tex>st</tex> сильно связанывзаимно достижимы в обоих графах. Те же рассуждения доказывают}} ==Время работы алгоритма==#Для того, чтобы инвертировать все ребра в графе, что представленном в виде списка потребуется <tex>tO(V + E)</tex> и действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования.#Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за <tex>rO(V + E)</tex> сильно связаны, из чего следует что #Поиск в глубину в исходном графе выполняется за <tex>tO(V + E)</tex> и .В итоге получаем, что время работы алгоритма <tex>sO(V + E)</tex> также сильно связаны.
==Пример реализацииПсевдокод== vectorПусть <vectortex>G<int/tex>— исходный граф, <tex> g, h; H<//g хранит tex> —инвертированный граф в виде списка смежностей, h - инвертированный vector. В массиве <inttex> color, ord, component; <//цвет вершины, список tex> будем хранить номера вершин в порядке окончания обработкипоиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, номер компоненты, к который относиться вершина int col; //каждой вершине сопоставляет номер текущей её компоненты.
==ЛитератураИсточники информации==
* Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002
* [http://e-maxx.ru/algo/strong_connected_components MAXimal :: algo :: Поиск компонент сильной связности, построение конденсации графа]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008/| Визуализация поиска компонент сильной связности]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]