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

28 января 2026Время чтения: 9 минут

#алгоритм Тарьяна#сильно связные компоненты#графы#DFS#SCC

В 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: $disc[1] = low[1] = 0$ , стек $[1]$ .
Идём по $1 \to 2$ . Заходим в 2: $disc[2] = low[2] = 1$ , стек $[1, 2]$ .
Идём по $2 \to 3$ . Заходим в 3: $disc[3] = low[3] = 2$ , стек $[1, 2, 3]$ .
Ребро $3 \to 1$ : 1 в стеке, значит $low[3] = \min(2, disc[1]) = 0$ .
Ребро $3 \to 4$ . Заходим в 4: $disc[4] = low[4] = 3$ , стек $[1, 2, 3, 4]$ .
Идём $4 \to 5$ . Заходим в 5: $disc[5] = low[5] = 4$ , стек $[1, 2, 3, 4, 5]$ .
Идём $5 \to 6$ . Заходим в 6: $disc[6] = low[6] = 5$ , стек $[1, 2, 3, 4, 5, 6]$ .
Ребро $6 \to 4$ : 4 в стеке, $low[6] = \min(5, disc[4]) = 3$ .
Ребро $6 \to 7$ . Заходим в 7: $disc[7] = low[7] = 6$ , стек $[1, 2, 3, 4, 5, 6, 7]$ . Соседей у 7 нет, проверяем $low[7] = disc[7] = 6$ - снимаем со стека SCC $\{7\}$ .
Возврат в 6: $low[6] = 3$ , $disc[6] = 5$ - не корень.
Возврат в 5: $low[5] = \min(4, low[6]) = 3$ - не корень.
Возврат в 4: $low[4] = \min(3, low[5]) = 3 = disc[4]$ - корень, снимаем со стека $\{4, 5, 6\}$ .
Возврат в 3: $low[3] = \min(0, low[4]) = 0$ - не корень.
Возврат в 2: $low[2] = \min(1, low[3]) = 0$ - не корень.
Возврат в 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 идея используется Тарьяном для мостов, точек сочленения и двусвязных компонент - освоить один из этих алгоритмов означает понять всё семейство.