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


Вместо вступления: обнаружил, что в сообществе нет статей хоть о каком-либо алгоритме поиска сильно связанных компонент. Посему решил чуток пополнить базу данных Хабра небольшой статьей.

Сразу к делу:

Напомним основные определения:

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

Пример сильно связного графа:

Заметим, что:

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

Тогда, компонентой сильной связности называется класс эквивалентности множества вершин ориентированного графа относительно отношения сильной связности.

Итак, наша задача найти все такие классы эквивалентности.

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

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

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

G' = (V, E') — граф, полученный инвертированием исходного графа G


Теперь выполним поиск в глубину на G'. Будем помечать время входа и время выхода (in/out). Заведем дополнительно массив вершин verticles. В него добавим все вершины в порядке увеличения времени выхода. Таким образом, массив verticles будет выглядеть следующим образом:


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


Вместо заключения:

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

Тем не менее, основная часть алгоритма состоит из двух обходов DFS. Каждый работает пропорционально V+E для разреженных графов и V^2 для насыщенных графов. Также нам требуется V памяти для хранения массива вершин.
-->


К сожалению, не доступен сервер mySQL