Алгоритм Косарайю: различия между версиями

(Показать все непатрулированные изменения)

[непроверенная версия]

Содержимое удалено Содержимое добавлено

Линейный

Текущая версия от 21:09, 24 октября 2024

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

Определения

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

Алгоритм

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

Свойство

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

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

Пример

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

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

Примечания

↑ Правильная транскрипция индийского имени — Косараджу, однако в русскоязычной литературе алгоритм традиционно носит имя Косарайю, см., например, «Алгоритмы на графах» Седжвика. Реже называется алгоритмом Косараю.

Ссылки

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

Литература

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

[1] Правильная транскрипция индийского имени — Косараджу, однако в русскоязычной литературе алгоритм традиционно носит имя Косарайю, см., например, «Алгоритмы на графах» Седжвика. Реже называется алгоритмом Косараю.

[1]

@@ Строка 1: / Строка 1: @@
-'''Алгоритм Косарайю''' - алгоритм поиска [[Компонента_сильной_связности_в_орграфе|компонент сильной связности]] в [[Граф_(математика)#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84|орграфе]]. Чтобы найти компоненты сильной связности, сначала выполняется [[Поиск_в_глубину|поиск в глубину]] на обращении исходного графа (ребра инвертированы), вычисляя вектор обратного порядка обхода. Затем мы используем обращение этого порядка, чтобы выполнить [[Поиск_в_глубину|поиск в глубину]] на исходном графе (в очередной раз берем вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты.
+'''Алгоритм Косарайю'''<ref>Правильная транскрипция индийского имени — Косараджу, однако в русскоязычной литературе алгоритм традиционно носит имя Косарайю, см., например, «Алгоритмы на графах» Седжвика. Реже называется алгоритмом Косараю.</ref> (в честь американского учёного индийского происхождения {{нп3|Самбасива Рао Косараджу|Самбасивы Рао Косараджу|en|S. Rao Kosaraju}}) — алгоритм поиска [[Компонента сильной связности в орграфе|областей сильной связности]] в [[Орграф|ориентированном графе]]. Чтобы найти области сильной связности, сначала выполняется [[поиск в глубину]] (DFS) на обращении исходного графа (то есть против дуг), вычисляя порядок ''выхода'' из вершин. Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берём вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты.
-==Определения==
+== Определения ==
+[[Ориентированный ациклический граф]] — это ориентированный граф, не содержащий направленных циклов.
+== Алгоритм ==
-Ориентированный ациклический граф (directed acyclic graph) - это [[Граф_(математика)#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84|орграф]], не содержащий направленных циклов.
+# Инвертируем дуги исходного ориентированного графа.
+# Запускаем поиск в глубину на этом обращённом графе, запоминая, в каком порядке выходили из вершин.
+# Запускаем поиск в глубину на исходном графе, в очередной раз выбирая не посещённую вершину с максимальным номером в векторе, полученном в п.2.
+# Полученные из п.3 деревья и являются сильно связными компонентами.
+== Свойство ==
-[[Топологическая_сортировка|Топологическая сортировка]] - упорядочивание [[Словарь терминов теории графов#К|бесконтурного]] [[Граф_(математика)#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84|орграфа]]  согласно [[Частичный порядок|частичному порядку]], заданному ребрами [[Граф_(математика)#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84|орграфа]] на множестве его вершин.
+'''Метод Косарайю обеспечивает поиск сильных компонент связности графа за линейное время и память.'''
+Доказательство:
-==Алгоритм==
-) Инвертируем ребра исходного [[Граф_(математика)#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84|орграфа]].
-) Запускаем [[Поиск_в_глубину|поиск в глубину]] на этом обращенном графе. В результате получаем вектор обхода.
-) Запускаем [[Поиск_в_глубину|поиск в глубину]] на исходном графе, в очередной раз выбирая не посещенную вершину с максимальным номером в порядке, полученном в п.2.
-) Полученные деревья леса [[Поиск_в_глубину|поиска в глубину]] и являются сильно связными компонентами.
-==Свойство==
-'''Метод Косарайю обеспечивает поиск сильных компонент связности графа ценой линейных затрат времени и памяти.'''
-Док-во:
 Этот метод состоит из двух процедур поиска в глубину, подвергнутых незначительным изменениям, в результате время его выполнения пропорционально V² в случае насыщенных графов и V + E в случае разреженных графов (если графы представлены в виде списков смежных вершин).
-==Пример==
+== Пример ==
+Ниже приведён пример работы алгоритма Косарайю.
+Чтобы вычислить сильные компоненты ориентированного графа, расположенного снизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева), вычисляя вектор обратного порядка обхода (Order). Этот порядок эквивалентен обратному порядку обхода леса DFS. Используя обращение этого порядка мы производим обход в глубину на исходном графе. То есть начинаем с вершины 3. Деревья в лесе DFS, которые выбираются в результате этого процесса, представляют собой сильные компоненты. Содержимое вектора id: номер компоненты, цифры слева — номер вершины.
-Ниже приведен пример работы алгоритма Косарайю.
-[[Изображение: Kosarayu.png‎|500px|center]]
-Чтобы вычислить сильные компоненты орграфа, расположенного снизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева), вычисляя вектор обратного порядка обхода. Этот порядок эквивалентен обратному порядку обхода леса DFS(вверху справа). Используя обращение этого порядка мы производим обход в глубину на исходном графе. Т.е. начинаем с 9. Деревья в лесе DFS, которые выбираются в результате этого процесса, представляют собой сильные компоненты. В векторе id: нижняяя строка - номер компоненты, верхняя - номер вершины.
-==Ссылки==
-* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008/ Визуализатор алгоритмов поиска компонент сильной связности]
+== Примечания ==
+{{примечания}}
+== Ссылки ==
+* [https://web.archive.org/web/20080531010721/http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008 Визуализатор алгоритмов поиска компонент сильной связности]
 == Литература ==
 * {{книга
 |автор = Роберт Седжвик.
@@ Строка 50: / Строка 40: @@
 |isbn = 5-93772-054-7
 }}
+{{Алгоритмы на графах}}
+{{нет сносок|дата=2012-10-07}}
 [[Категория:Алгоритмы на графах]]
+[[Категория:Связность графа]]

Алгоритмы на графах
Поиск уплотнений	Алгоритм Брона — Кербоша Алгоритм Косарайю Алгоритм Мальгранжа Алгоритм Тарьяна Алгоритм Демукрона Приближенный алгоритм поиска p-медиан Задача о самом длинном пути Топологическая сортировка Шарнир (теория графов) Алгоритм Каргера (минимальный разрез)
Максимизация потока	Алгоритм Диница Алгоритм Малхотры — Кумара — Махешвари Алгоритм проталкивания предпотока Алгоритм Форда — Фалкерсона Алгоритм Эдмондса — Карпа Транспортная сеть
Паросочетания	Алгоритм сжатия цветков Алгоритм Хопкрофта — Карпа Алгоритм FKT
Связь графов	Алгоритм Гавела — Хакими(графичность последовательности) Расстояние редактирования графа Задача поиска изоморфного подграфа
Другое	Алгоритм для дерева сочленений (извлекает маргинализацию) Алгоритм Катхилл — Макки (уменьшения ширины ленты) Итеративное сжатие (идея рекурсии) Шаблон:Алгоритмы поиска на графах