Pull to refresh

Поиск компонент сильной связности: алгоритм Косарайю

Reading time 2 min
Views 38K
На хабре нет ни одной статьи о поиске компонент сильной связности. Однако это интересная задача, имеющая приложения в самых разных сферах: системах рекомендаций, математической логике и, неожиданно, экологии. Ниже формулировка задачи и решение — алгоритм Косарайю.

К делу:

  • Две вершины ($u$ и $v$) ориентированного графа называют сильно связными, если существует путь из $u$ в $v$ и существует путь из $v$ в $u$.
  • Ориентированный граф называется сильно связным, если любые две его вершины сильно связны.



Заметим: отношение сильной связности — это отношение эквивалентности.

$1)Рефлексивность:\ \forall v\ v \to v$
$2)Симметричность:\ \forall v\ \forall u\ v \to u => u \to v$
$3) Транзитивность: \forall v\ \forall u\ \forall t\ v \to u \ \wedge u \to t => v \to t $

Компонентой сильной связности называется класс эквивалентности множества вершин ориентированного графа относительно отношения сильной связности. Другими словами компонента сильной связности = сильно связный подграф. Так как сильная связность — это отношение эквивалентности, то граф разбивается на сильно связные компоненты. Наша задача найти все такие классы эквивалентности.



Алгоритм Косарайю

  • Инвертированием ориентированного графа назовем процедуру, в ходе которой поменяем направление каждого ребра на противоположное.

Метод Косарайю прост для реализации и понимания. Так как компоненты сильной связности есть циклы, то они совпадают и у исходного графа и у его инвертирования.

Пусть дан ориентированный граф G = (V, E). Через G' = (V, E') обозначим интертирование G.

Будем обходить граф G в глубину, пока не посетим все вершины. Заведем массив out = [0...|V|-1] — время выхода из вершины. Под временем понимаются логические часы: изначально время равно 0, при переходе в вершину или выходе из неё время увеличивается на 1.


Когда обход закончится, заведем массив vertices, куда добавим все вершины в порядке увеличения времени выхода. Теперь запустим обход в глубинку на инвертированном графе G'. Каждый раз для обхода будем выбирать ещё не посещенную вершину с максимальным индексом в массиве vertices. Все вершины, посещенные в ходе одной итерации dfs, образуют компоненту сильной связности.



Время работы

Заметим: если граф представлен графом смежности, то нам не требуетcя хранить в памяти инвертированный граф. Иначе нам потребуется O(V+E) доп. памяти. Но, в любом случае, нам требуется O(V) памяти для массивов out и vertices.

Алгоритм состоит из двух обходов DFS. Каждый работает пропорционально V+E для разреженных графов и V^2 для насыщенных. Кроме того, нам требуется O(VlogV) для сортировки вершин при построении массива vertices.

Дополнительно

Корректность алгоритма и псевдокод можно посмотреть тут: www.jeffreykarres.com/blog/kosaraju

В начале статьи я упоминал приложения.
Tags:
Hubs:
+17
Comments 7
Comments Comments 7

Articles