Главная
Статьи





07.11.2022


07.11.2022


07.11.2022


06.11.2022


06.11.2022






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

21.01.2022

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

Определения

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

Алгоритм

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

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

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

    Пример

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

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