Алгоритм Косарайю

Алгоритм Косарайю - алгоритм поиска компонент сильной связности в орграфе. Чтобы найти компоненты сильной связности, сначала выполняется поиск в глубину на обращении исходного графа (ребра инвертированы), вычисляя вектор обратного порядка обхода. Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берем вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты.

Определения

Ориентированный ациклический граф (directed acyclic graph) - это орграф, не содержащий направленных циклов.

Топологическая сортировка - упорядочивание бесконтурного орграфа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.

Алгоритм

1) Инвертируем ребра исходного орграфа.

2) Запускаем поиск в глубину на этом обращенном графе. В результате получаем вектор обхода.

3) Запускаем поиск в глубину на исходном графе, в очередной раз выбирая не посещенную вершину с максимальным номером в порядке, полученном в п.2.

4) Полученные деревья леса поиска в глубину и являются сильно связными компонентами.

Свойство

Метод Косарайю обеспечивает поиск сильных компонент связности графа ценой линейных затрат времени и памяти.

Док-во: Этот метод состоит из двух процедур поиска в глубину, подвергнутых незначительным изменениям, в результате время его выполнения пропорционально V² в случае насыщенных графов и V + E в случае разреженных графов (если графы представлены в виде списков смежных вершин).

Пример

Ниже приведен пример работы алгоритма Косарайю.

Файл:Kosarayu.png

Чтобы вычислить сильные компоненты орграфа, расположенного снизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева), вычисляя вектор обратного порядка обхода. Этот порядок эквивалентен обратному порядку обхода леса DFS(вверху справа). Используя обращение этого порядка мы производим обход в глубину на исходном графе. Т.е. начинаем с 9. Деревья в лесе DFS, которые выбираются в результате этого процесса, представляют собой сильные компоненты. В векторе id: нижняяя строка - номер компоненты, верхняя - номер вершины.

Ссылки

• Визуализатор алгоритмов поиска компонент сильной связности

Литература

• Роберт Седжвик. Алгоритмы на графах = Graph algorithms. — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофтЮП», 2002. — С. 496. — ISBN 5-93772-054-7.