1632
правки
Изменения
м
rollbackEdits.php mass rollback
Пусть <tex>G</tex> — исходный граф, <tex>H</tex> —инвертированный граф. В массиве <tex>ord</tex> будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, который каждой вершине сопоставляет номер её компоненты.
'''function''' dfs1(v) :
color[v] = 1
'''for''' (всех i смежных с v, u)'''in''' E '''if''' (вершина i не посещена)'''not''' visited[u] dfs1(G[v][iu])
Добавляем вершину v в конец списка ord
'''function''' dfs2(v) :
component[v] = col
'''for''' (всех i смежных с v, u)'''in''' E '''if''' (если вершина i u еще не находится ни в какой компоненте) dfs2(H[v][iu])
'''function''' main():
считываем исходные данные, формируем массивы G и H
'''for''' (по всем вершинам i графа G) u '''in''' V '''if''' (вершина i не посещена)'''not''' visited[u] dfs1(iu)
col = 1
'''for''' (по всем вершинам i u списка ord[] в обратном порядке) '''if''' (если вершина i u не находится ни в какой компоненте) dfs2(iu)
col++
* Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002
* [http://e-maxx.ru/algo/strong_connected_components MAXimal :: algo :: Поиск компонент сильной связности, построение конденсации графа]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008/| Визуализация поиска компонент сильной связности]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
