Вместо вступления: обнаружил, что в сообществе нет статей хоть о каком-либо алгоритме поиска сильно связанных компонент. Посему решил чуток пополнить базу данных Хабра небольшой статьей.
Сразу к делу:
Напомним основные определения:
- Две вершины ($inline$u$inline$ и $inline$v$inline$) ориентированного графа называют сильно связными, если существует путь из $inline$u$inline$ в $inline$v$inline$ и существует путь из $inline$v$inline$ в $inline$u$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 памяти для хранения массива вершин.
Автор: Faunuss
Спасибо за статью, а то на хабре без картинок