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

в 9:02, , рубрики: Алгоритмы, графы

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

Сразу к делу:

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

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

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

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

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

Отношение сильной связности - это отношение эквивалентности.

$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).

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

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

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

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

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

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

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

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

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

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

Автор: Faunuss

Источник

Поделиться

  1. Дмитрий:

    Спасибо за статью, а то на хабре без картинок

* - обязательные к заполнению поля