Поиск компонент сильной связности: алгоритм Косарайю +17
Алгоритмы
Рекомендация: подборка платных и бесплатных курсов дизайна интерьера - https://katalog-kursov.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 памяти для хранения массива вершин.
-->
К сожалению, не доступен сервер mySQL