Алгоритм Косарайю
Алгоритм Косарайю[1] (в честь американского учёного индийского происхождения Самбасивы Рао Косараджу[англ.]) — алгоритм поиска областей сильной связности в ориентированном графе. Чтобы найти области сильной связности, сначала выполняется поиск в глубину (DFS) на обращении исходного графа (то есть против дуг), вычисляя порядок выхода из вершин. Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берём вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты.
Определения
[править | править код]Ориентированный ациклический граф — это ориентированный граф, не содержащий направленных циклов.
Алгоритм
[править | править код]- Инвертируем дуги исходного ориентированного графа.
- Запускаем поиск в глубину на этом обращённом графе, запоминая, в каком порядке выходили из вершин.
- Запускаем поиск в глубину на исходном графе, в очередной раз выбирая не посещённую вершину с максимальным номером в векторе, полученном в п.2.
- Полученные из п.3 деревья и являются сильно связными компонентами.
Свойство
[править | править код]Метод Косарайю обеспечивает поиск сильных компонент связности графа за линейное время и память.
Доказательство: Этот метод состоит из двух процедур поиска в глубину, подвергнутых незначительным изменениям, в результате время его выполнения пропорционально V² в случае насыщенных графов и V + E в случае разреженных графов (если графы представлены в виде списков смежных вершин).
Пример
[править | править код]Ниже приведён пример работы алгоритма Косарайю.
Чтобы вычислить сильные компоненты ориентированного графа, расположенного снизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева), вычисляя вектор обратного порядка обхода (Order). Этот порядок эквивалентен обратному порядку обхода леса DFS. Используя обращение этого порядка мы производим обход в глубину на исходном графе. То есть начинаем с вершины 3. Деревья в лесе DFS, которые выбираются в результате этого процесса, представляют собой сильные компоненты. Содержимое вектора id: номер компоненты, цифры слева — номер вершины.
Примечания
[править | править код]- ↑ Правильная транскрипция индийского имени — Косараджу, однако в русскоязычной литературе алгоритм традиционно носит имя Косарайю, см., например, «Алгоритмы на графах» Седжвика. Реже называется алгоритмом Косараю.
Ссылки
[править | править код]Литература
[править | править код]- Роберт Седжвик. Алгоритмы на графах = Graph algorithms. — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофтЮП», 2002. — С. 496. — ISBN 5-93772-054-7.
| Поиск уплотнений | |
|---|---|
| Максимизация потока | |
| Паросочетания | |
| Связь графов |
|
| Другое |
|
 | В статье есть список источников, но не хватает сносок. |