Алгоритм КосарайюПравильная транскрипция индийского имени — Косараджу, однако в русскоязычной литературе алгоритм традиционно носит имя Косарайю, см., например, «Алгоритмы на графах» Седжвика. Реже называется алгоритмом Косараю. (в честь американского учёного индийского происхождения ) — алгоритм поиска областей сильной связности в ориентированном графе. Чтобы найти области сильной связности, сначала выполняется поиск в глубину (DFS) на обращении исходного графа (то есть против дуг), вычисляя порядок выхода из вершин. Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берём вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты.

Определения Ориентированный ациклический граф — это ориентированный граф, не содержащий направленных циклов.

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

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

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

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

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

Примечания

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

Литература

Категория:Алгоритмы на графах Категория:Связность графа