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

Сразу к делу:

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

• Две вершины ($\$inline\$u\$inline\$$ и $\$inline\$v\$inline\$$) ориентированного графа называют сильно связными, если существует путь из $\$inline\$u\$inline\$$ в $\$inline\$v\$inline\$$ и существует путь из $\$inline\$v\$inline\$$ в $\$inline\$u\$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 памяти для хранения массива вершин.