Алгоритм Тарьяна: поиск компонент связности орграфа

В 1972 году Роберт Тарьян опубликовал короткую статью «Depth-first search and linear graph algorithms», в которой описал, как за один проход поиска в глубину найти все сильно связные компоненты ориентированного графа. Алгоритм Тарьяна работает за линейное время $O(V + E)$, использует один стек и два целочисленных массива на вершину. С тех пор он стал стандартным способом раскладывать орграф на максимальные «куски замкнутой циркуляции» - для компиляторов, систем зависимостей, 2-SAT и любых задач, где важно понимать структуру циклов.

Что такое сильно связная компонента

Сильно связная компонента (strongly connected component, SCC) орграфа $G = (V, E)$ - это максимальное по включению подмножество вершин $C \subseteq V$, такое что для любой пары $u, v \in C$ существует ориентированный путь $u \to v$ и обратный путь $v \to u$. Иначе говоря, внутри SCC из любой вершины можно дойти до любой другой, двигаясь только по стрелкам.

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

Важно не путать с неориентированным случаем: там понятия «связная компонента» и «сильно связная компонента» совпадают - нет направления, достижимость симметрична автоматически. SCC становятся содержательным понятием только на орграфах.

Идея алгоритма

Алгоритм Тарьяна делает один обход DFS и поддерживает для каждой вершины $v$ два числа:

• $disc[v]$ - discovery time, момент первого посещения (номер вызова DFS).
• $low[v]$ - минимальное значение $disc$, достижимое из поддерева DFS с корнем $v$, если разрешить максимум одно «обратное» ребро в текущую активную ветку.

Параллельно ведётся стек активных вершин: каждая новая вершина кладётся на стек при первом посещении и снимается, только когда обнаруживается, что она - корень SCC. Флаг onStack[v] за $O(1)$ отличает «вершину в текущем поддереве» от «вершины уже закрытой SCC».

Ключ: если для $v$ после обработки всех детей $disc[v] = low[v]$, то из поддерева $v$ нельзя «убежать» в более ранний узел текущей цепочки - значит, $v$ является корнем своей SCC. Выгружаем со стека всё до $v$ включительно - это и есть очередная компонента.

Псевдокод

time = 0
stack = []
SCCs = []

def strongconnect(v):
    disc[v] = low[v] = time
    time += 1
    stack.append(v)
    onStack[v] = True

    for w in adj[v]:
        if disc[w] is undefined:
            strongconnect(w)                # дерево DFS
            low[v] = min(low[v], low[w])
        elif onStack[w]:
            low[v] = min(low[v], disc[w])   # обратное / поперечное в текущую ветку
        # иначе ребро в уже закрытую SCC - игнорируем

    if low[v] == disc[v]:                   # v - корень SCC
        comp = []
        while True:
            w = stack.pop()
            onStack[w] = False
            comp.append(w)
            if w == v:
                break
        SCCs.append(comp)

for v in V:
    if disc[v] is undefined:
        strongconnect(v)

Все три ветки существенны: первая объединяет поддеревья детей, вторая ловит back/cross-edges внутри текущей ветки, третья игнорирует рёбра в уже свёрнутые SCC - они справа в конденсации и не вернут нас назад.

Подробный пример

Возьмём орграф из 7 вершин и 8 рёбер: $1 \to 2,\ 2 \to 3,\ 3 \to 1,\ 3 \to 4,\ 4 \to 5,\ 5 \to 6,\ 6 \to 4,\ 6 \to 7$. Запустим DFS из вершины 1.

1. Заходим в 1: $disc[1] = low[1] = 0$, стек $[1]$.
2. Идём по $1 \to 2$. Заходим в 2: $disc[2] = low[2] = 1$, стек $[1, 2]$.
3. Идём по $2 \to 3$. Заходим в 3: $disc[3] = low[3] = 2$, стек $[1, 2, 3]$.
4. Ребро $3 \to 1$: 1 в стеке, значит $low[3] = \min(2, disc[1]) = 0$.
5. Ребро $3 \to 4$. Заходим в 4: $disc[4] = low[4] = 3$, стек $[1, 2, 3, 4]$.
6. Идём $4 \to 5$. Заходим в 5: $disc[5] = low[5] = 4$, стек $[1, 2, 3, 4, 5]$.
7. Идём $5 \to 6$. Заходим в 6: $disc[6] = low[6] = 5$, стек $[1, 2, 3, 4, 5, 6]$.
8. Ребро $6 \to 4$: 4 в стеке, $low[6] = \min(5, disc[4]) = 3$.
9. Ребро $6 \to 7$. Заходим в 7: $disc[7] = low[7] = 6$, стек $[1, 2, 3, 4, 5, 6, 7]$. Соседей у 7 нет, проверяем $low[7] = disc[7] = 6$ - снимаем со стека SCC $\{7\}$.
10. Возврат в 6: $low[6] = 3$, $disc[6] = 5$ - не корень.
11. Возврат в 5: $low[5] = \min(4, low[6]) = 3$ - не корень.
12. Возврат в 4: $low[4] = \min(3, low[5]) = 3 = disc[4]$ - корень, снимаем со стека $\{4, 5, 6\}$.
13. Возврат в 3: $low[3] = \min(0, low[4]) = 0$ - не корень.
14. Возврат в 2: $low[2] = \min(1, low[3]) = 0$ - не корень.
15. Возврат в 1: $low[1] = \min(0, low[2]) = 0 = disc[1]$ - корень, снимаем $\{1, 2, 3\}$.

Итого три SCC: $\{1, 2, 3\}$, $\{4, 5, 6\}$, $\{7\}$. Стек пуст, обход закончен.

Сложность и сравнение

Каждое ребро рассматривается ровно один раз (как древесное или как back/cross), каждая вершина один раз попадает на стек и один раз снимается с него. Память - $O(V)$ под массивы $disc$, $low$, onStack и сам стек. Итог: $O(V + E)$ времени, $O(V)$ памяти.

Альтернатива - алгоритм Косарайю (1978): сначала DFS на исходном графе с сохранением порядка завершения, затем DFS на транспонированном графе $G^T$ в обратном порядке. Та же асимптотика $O(V + E)$, но Косарайю требует построения $G^T$ и делает две DFS вместо одной - лишний проход и удвоенная память на списки смежности. Константа Тарьяна меньше; на больших разреженных графах разница заметна, особенно при кэш-локальности обходов. Алгоритм Габова (1999) - ещё одна альтернатива с двумя стеками вместо $low$, асимптотика та же, на практике используется реже.

Применения

• Системы пакетных зависимостей. Cargo, npm, Gradle ищут SCC в графе «пакет → зависит от», чтобы детектировать циклы - нормальный граф зависимостей обязан быть DAG.
• 2-SAT за линейное время. Формулу 2-SAT сводят к импликационному графу с $2n$ вершинами; формула выполнима тогда и только тогда, когда никакая переменная $x_i$ и её отрицание $\neg x_i$ не лежат в одной SCC.
• Dataflow-анализ компилятора. На графе вызовов или CFG SCC соответствуют взаимно-рекурсивным группам функций - их обрабатывают единым блоком.
• Достижимость и редукция. Стягивание SCC превращает орграф в DAG, на котором быстро считаются транзитивное замыкание и топологический порядок.

Связь с другими алгоритмами Тарьяна

Роберт Тарьян - лауреат Тьюринговской премии 1986 года - придумал целое семейство алгоритмов на DFS-временах с похожей low-link идеей:

• Поиск мостов в неориентированном графе - ребро $(u, v)$ является мостом, если $low[v] > disc[u]$, где $v$ - потомок $u$ в дереве DFS. Алгоритм почти идентичен; разница в учёте ребра родителя.
• Поиск точек сочленения (cut vertices) - вершина $v$ является точкой сочленения, если у неё в дереве DFS есть ребёнок $w$ с $low[w] \ge disc[v]$ (с особым случаем корня).
• Двусвязные компоненты (biconnected components) - на схожем стеке, но из рёбер.
• Union-Find с path compression и union by rank - структура с почти-константной амортизированной сложностью $O(\alpha(n))$ за операцию, фундамент для Краскала.

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

Частые ошибки

• Перепутать $low[w]$ и $disc[w]$ в обратном ребре. При обработке back-edge берётся именно $disc[w]$ - $low[w]$ ещё не окончательно посчитан. Современные изложения допускают $low[w]$: даёт тот же ответ, но скрывает инвариант.
• Забыть флаг onStack. Без него обратное ребро в уже закрытую SCC ошибочно уменьшит $low[v]$ и сольёт две разные компоненты.
• Использовать рекурсию на больших графах. Стек вызовов Python / JVM ограничен; на графах в миллионы вершин нужна итеративная версия с явным стеком фреймов.
• Применять алгоритм к неориентированному графу как есть. Для неориентированного графа задача SCC бессмысленна (= обычная связность через BFS/Union-Find); Тарьян здесь решает другие задачи - мосты и точки сочленения.
• Считать, что порядок вершин внутри SCC что-то значит. Алгоритм возвращает SCC как множества; порядок в стеке зависит от обхода и не несёт смысловой нагрузки.

FAQ

Чем алгоритм Тарьяна лучше Косарайю? Одной DFS вместо двух и без построения транспонированного графа. На больших разреженных графах работает заметно быстрее на практике, хотя асимптотически оба $O(V + E)$. Косарайю проще объяснить «на пальцах», но Тарьян выигрывает в коде и в памяти.

Можно ли искать SCC через BFS? В общем случае нет: BFS не даёт естественного понятия «время выхода» и «поддерева», на котором построен low-link. Существуют BFS-варианты для частных случаев (плоские графы), но универсальный линейный алгоритм SCC требует DFS.

Что если граф не связен? Внешний цикл for v in V запускает $strongconnect$ из каждой непосещённой вершины - алгоритм корректно обработает любое число слабо связных частей. Отдельная проверка связности не нужна.

Коротко

Алгоритм Тарьяна находит все сильно связные компоненты орграфа за один проход DFS и время $O(V + E)$, поддерживая для каждой вершины время первого посещения $disc[v]$, минимальное достижимое из поддерева $low[v]$ и стек активных вершин. Корнем SCC оказывается вершина, у которой $disc[v] = low[v]$; на этом моменте стек выгружается до неё. Та же low-link идея используется Тарьяном для мостов, точек сочленения и двусвязных компонент - освоить один из этих алгоритмов означает понять всё семейство.