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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определения[править | править исходный текст]

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

Алгоритм[править | править исходный текст]

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

Свойство[править | править исходный текст]

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

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

Пример[править | править исходный текст]

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

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

Ссылки[править | править исходный текст]

Литература[править | править исходный текст]

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