Изменения
→Псевдокод
==Алгоритм==
[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]]
[[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связанностисвязности]] в графе <tex>G</tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 3 этапа:
#Построить граф <tex>H</tex> с обратными (инвертированными) рёбрами
#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> — время окончания обработки вершины <tex>u</tex>
<tex>\Leftarrow</tex>
}}
Пусть <tex>G</tex> — исходный граф, <tex>H</tex> —инвертированный граф. В массиве <tex>ord</tex> будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, который каждой вершине сопоставляет номер её компоненты.
'''dfs1function'''dfs1(<tex>v</tex>) : <tex>color[v] \leftarrow = 1</tex> '''for''' (всех <tex>i</tex> смежных с <tex>v</tex>, u)'''in''' E '''if''' (вершина <tex>i</tex> не посещена) '''dfs1not'''visited[u] dfs1(<tex>G[v][iu]</tex>) Добавляем вершину <tex>v</tex> в конец списка <tex>ord</tex>
'''dfs2function'''dfs2(<tex>v</tex>) : <tex>component[v] \leftarrow = col</tex> '''for''' (всех <tex>i</tex> смежных с <tex>v</tex>, u)'''in''' E '''if''' (если вершина <tex>i</tex> u еще не находится ни в какой компоненте) '''dfs2'''(<tex>H[v][iu]</tex>)
'''mainfunction'''main(): считываем исходные данные, формируем массивы <tex>G</tex> и <tex>H</tex> '''for''' (по всем вершинам <tex>i</tex> графа <tex>G</tex>) u '''in''' V '''if''' (вершина <tex>i</tex> не посещена) '''dfs1not'''visited[u] dfs1(iu) <tex>col \leftarrow = 1</tex> '''for''' (по всем вершинам <tex>i</tex> u списка <tex>ord[]</tex> в обратном порядке) '''if''' (если вершина <tex>i</tex> u не находится ни в какой компоненте) '''dfs2'''(<tex>i</tex>u) <tex>col</tex>++
==ЛитератураИсточники информации==
* Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002
* [http://e-maxx.ru/algo/strong_connected_components MAXimal :: algo :: Поиск компонент сильной связности, построение конденсации графа]* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008/| Визуализация поиска компонент сильной связности]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]