Алгоритм Косарайю: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0 |
Rubinbot (обсуждение | вклад) м Бот: добавление заголовков в сноски; исправление двойных сносок, см. ЧаВо |
||
| (не показаны 4 промежуточные версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
'''Алгоритм |
'''Алгоритм Косарайю'''<ref>Правильная транскрипция индийского имени — Косараджу, однако в русскоязычной литературе алгоритм традиционно носит имя Косарайю, см., например, «Алгоритмы на графах» Седжвика. Реже называется алгоритмом Косараю.</ref> (в честь американского учёного индийского происхождения {{нп3|Самбасива Рао Косараджу|Самбасивы Рао Косараджу|en|S. Rao Kosaraju}}) — алгоритм поиска [[Компонента сильной связности в орграфе|областей сильной связности]] в [[Орграф|ориентированном графе]]. Чтобы найти области сильной связности, сначала выполняется [[поиск в глубину]] (DFS) на обращении исходного графа (то есть против дуг), вычисляя порядок ''выхода'' из вершин. Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берём вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты. |
||
== Определения == |
== Определения == |
||
| Строка 11: | Строка 11: | ||
== Свойство == |
== Свойство == |
||
'''Метод |
'''Метод Косарайю обеспечивает поиск сильных компонент связности графа за линейное время и память.''' |
||
Доказательство: |
Доказательство: |
||
| Строка 17: | Строка 17: | ||
== Пример == |
== Пример == |
||
Ниже приведён пример работы алгоритма |
Ниже приведён пример работы алгоритма Косарайю. |
||
Чтобы вычислить сильные компоненты ориентированного графа, расположенного снизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева), вычисляя вектор обратного порядка обхода (Order). Этот порядок эквивалентен обратному порядку обхода леса DFS. Используя обращение этого порядка мы производим обход в глубину на исходном графе. То есть начинаем с вершины 3. Деревья в лесе DFS, которые выбираются в результате этого процесса, представляют собой сильные компоненты. Содержимое вектора id: номер компоненты, цифры слева — номер вершины. |
Чтобы вычислить сильные компоненты ориентированного графа, расположенного снизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева), вычисляя вектор обратного порядка обхода (Order). Этот порядок эквивалентен обратному порядку обхода леса DFS. Используя обращение этого порядка мы производим обход в глубину на исходном графе. То есть начинаем с вершины 3. Деревья в лесе DFS, которые выбираются в результате этого процесса, представляют собой сильные компоненты. Содержимое вектора id: номер компоненты, цифры слева — номер вершины. |
||
== Примечания == |
|||
{{примечания}} |
|||
== Ссылки == |
== Ссылки == |
||
| Строка 38: | Строка 41: | ||
}} |
}} |
||
{{Алгоритмы на графах}} |
|||
{{нет сносок}} |
{{нет сносок|дата=2012-10-07}} |
||
[[Категория:Алгоритмы на графах]] |
[[Категория:Алгоритмы на графах]] |
||
[[Категория:Связность графа]] |
|||
Текущая версия от 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.
| Поиск уплотнений | |
|---|---|
| Максимизация потока | |
| Паросочетания | |
| Связь графов |
|
| Другое |
|
 | В статье есть список источников, но не хватает сносок. |