Информатика / Алгоритмы и анализ данных

Сильные компоненты: два обхода алгоритма Косарайю

Сильная компонента ориентированного графа объединяет вершины, достижимые друг из друга в обоих направлениях. Алгоритм Косарайю находит такие группы двумя обходами в глубину с разворотом всех дуг.

Опубликовано: 21 октября 2026 г.Обновлено: 21 октября 2026 г.

Формула

u\sim v\iff(u\leadsto v)\land(v\leadsto u),\qquad T=O(|V|+|E|)

Схема Сильные компоненты: AB | CD | E

Взаимная достижимость: {A,B}, {C,D}, {E}

Обозначения

$u\leadsto v$: существует ориентированный путь из u в v, логическое условие
$G^T$: граф с теми же вершинами и всеми развёрнутыми дугами, не применяется
$t_{out}$: время завершения вершины при первом DFS, номер события
$|V|,|E|$: число вершин и дуг, целые неотрицательные числа

Условия применения

Граф конечен и ориентирован. В описанном варианте первый полный DFS выполняется по транспонированному графу, а второй — по исходному, в порядке убывания времён завершения первого обхода. Между фазами метки посещения обнуляют; новая вершина второго обхода начинает отдельную компоненту.

Ограничения

Достижимость только в одну сторону не означает принадлежности одной сильной компоненте. Нельзя менять граф одной фазы, сохраняя порядок из другого варианта без обоснования. Номера компонент произвольны и не измеряют расстояние. Для больших графов нужно контролировать память списков и глубину стека.

Подробное объяснение

Отношение взаимной достижимости разбивает вершины на непересекающиеся группы. Внутри такой группы из любой вершины можно прийти в любую другую, следуя направлениям дуг. Одна вершина без петли тоже образует сильную компоненту: путь нулевой длины обеспечивает достижимость самой себя.

Если каждую компоненту сжать в одну вершину, получится конденсация. Она всегда ациклична: цикл между разными группами сделал бы все его вершины взаимно достижимыми и объединил бы их в одну группу. Алгоритм использует эту структуру, хотя заранее компоненты неизвестны.

В первом проходе разворачивают все дуги и строят порядок завершения полного DFS. В обратном порядке завершения вершины подходящей стоковой компоненты исходного графа окажутся раньше компонент, в которые из неё можно было бы ошибочно уйти. Второй обход по исходным дугам выделяет такую группу целиком и не захватывает ещё не обработанную внешнюю группу.

После выделения группы её вершины остаются помеченными, и следующий старт пропускает их. Можно понимать процесс как последовательное удаление стоковых компонент конденсации. Есть и симметричный вариант: сначала исходный граф, затем транспонированный; важно согласованно изменить обе фазы.

Построение обратных списков и каждый полный обход требуют O(|V|+|E|). Общая линейность сохраняется, потому что число фаз постоянно. После разбиения любые два идентификатора вершин сравнивают по номеру компоненты, но эти номера имеют смысл только в пределах конкретного запуска.

Как пользоваться формулой

Постройте транспонированный граф, разворачивая каждую дугу и сохраняя все вершины, включая изолированные.
Выполните полный DFS по обратным дугам и сохраните вершины в порядке завершения, а не первого открытия.
Обнулите метки посещения и обходите исходный граф из стартов в обратном порядке сохранённого завершения.
Каждый новый запуск второй фазы помечайте отдельным номером компоненты; проверьте взаимную достижимость на малом примере.

Историческая справка

Двухпроходный метод принят в учебной литературе под названием алгоритма Косарайю; реализация Принстонского курса использует название Kosaraju–Sharir. Рядом с ним существует другой линейный подход Тарьяна, опубликованный в 1972 году и использующий один обход с дополнительным стеком. Это разные алгоритмы для одной задачи, и переносить служебные правила одного в другой нельзя. Современное изложение через транспонирование и конденсацию удобно тем, что отделяет понятие сильной компоненты от конкретного способа её поиска. В статье Тарьяна исторически подчёркнута роль DFS в линейном анализе ориентированных графов, тогда как показанная здесь программа следует двухпроходной учебной схеме. Точная дата первого появления этой версии по используемым материалам не устанавливается.

Историческая линия формулы

Здесь описан двухпроходный алгоритм Косарайю с первым обходом по транспонированному графу. Название Kosaraju–Sharir встречается в источнике Принстонского курса. Его не следует называть однопроходным алгоритмом Тарьяна: совпадает задача, но отличаются порядок работы и необходимые данные.

Пример

В графе заданы A→B, B→A, B→C, C→D, D→C, D→E. В транспонированном графе стартуем с A и читаем соседей алфавитно. Первый обход завершает B, затем A; следующий старт C завершает D, затем C; последний E завершает E. Обратный порядок завершения E,C,D,A,B задаёт старты второй фазы по исходным дугам. Из E получаем группу {E}. Из C достигаем D и уже отмеченной E, поэтому новая группа {C,D}. Из A получаем {A,B}, а C уже отмечена. Всего три сильные компоненты. Их конденсация — цепочка {A,B}→{C,D}→{E}. Из A достижима E, но обратного пути нет, поэтому объединять их нельзя.

Частая ошибка

Не заменяйте взаимную достижимость обычной связностью после удаления стрелок. Не используйте порядок открытия вместо обратного завершения. Не забывайте обнулить посещения между фазами. Не начинайте второй проход на том же направлении дуг. Не считайте идентификатор компоненты её размером или номером шага кратчайшего пути.

Практика

Задачи с решением

Цикл и одиночная вершина

Условие. Дуги A→B, B→C, C→A и изолированная D. Сколько сильных компонент?

Решение. По циклу A,B,C взаимно достижимы. Изолированная D образует собственную компоненту. Итого две группы.

Ответ. 2: {A,B,C} и {D}.

Добавление обратного пути

Условие. В примере с компонентами {A,B}→{C,D}→{E} добавьте E→A. Что произойдёт?

Решение. Все группы окажутся на ориентированном цикле конденсации. Теперь из любой вершины есть путь в любую другую через эту цепочку и обратную дугу.

Ответ. Одна сильная компонента из 5 вершин.

Дополнительные источники

https://algs4.cs.princeton.edu/42digraph/KosarajuSharirSCC.java.html
https://stanford-cs161.github.io/winter2024/assets/files/lecture10-slides.pdf
https://www.cs.cmu.edu/~cdm/resources/Tarjan1972-sccs.pdf

Связанные формулы

Информатика

Поиск в глубину: дерево обхода и времена входа и выхода

$u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v$

Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.

Информатика

Топологическая сортировка Кана по входящим степеням

$d_{in}(v)\leftarrow d_{in}(v)-1\quad\text{при удалении дуги }u\to v;\qquad |L|=|V|\iff G\text{ ацикличен}$

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

Информатика

Мосты графа: критерий через времена входа и low

$(v,u)\text{ — мост}\iff low(u)>t_{in}(v),\quad u\text{ — ребёнок }v\text{ в DFS}$

Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. DFS обнаруживает его, если поддерево ребёнка не имеет обходного ребра к родителю или его предкам.

Информатика

Точки сочленения: критерий low и отдельное правило корня

$v\ne root:\quad v\text{ — точка сочленения}\iff\exists u\text{ — ребёнок}:low(u)\ge t_{in}(v)$

Точка сочленения — вершина, удаление которой вместе с инцидентными рёбрами увеличивает число компонент связности. Для некорневой вершины DFS использует нестрогое сравнение low ребёнка с временем входа.