- PVSM.RU - https://www.pvsm.ru -
Вместо вступления: обнаружил, что в сообществе нет статей хоть о каком-либо алгоритме поиска сильно связанных компонент. Посему решил чуток пополнить базу данных Хабра небольшой статьей.
Сразу к делу:
Напомним основные определения:
Пример сильно связного графа:
Заметим, что:
Тогда, компонентой сильной связности называется класс эквивалентности множества вершин ориентированного графа относительно отношения сильной связности.
Итак, наша задача найти все такие классы эквивалентности.
Алгоритм Косарайю
Метод Косарайю достаточно прост для реализации и понимания. Идея состоит в том, что у исходного графа и его инвертирования совпадают компоненты сильной связности (т.к они по сути являются циклами).
Пусть дан ориентированный граф 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
Источник [1]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/259132
Ссылки в тексте:
[1] Источник: https://habrahabr.ru/post/331904/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox
Нажмите здесь для печати.