Алгоритм Косараджу: Руководство по компонентам сильной связности

Алгоритм Косараджу находит компоненты сильной связности (КСС) ориентированного графа. КСС — это группа вершин, в которой из любой вершины можно добраться до любой другой. Алгоритм выполняет два обхода в глубину: первый записывает порядок, в котором вершины завершают обработку, а второй запускается на графе с обратными рёбрами, обходя вершины в порядке, обратном порядку завершения. Каждое дерево второго обхода — это одна КСС. Алгоритм работает за O(V + E).

Если сжать каждую КСС в одну вершину, получится ориентированный граф без циклов. Именно поэтому КСС применяются в анализе зависимостей, обнаружении взаимоблокировок, 2-SAT и в любой задаче, где сначала нужно свернуть циклы.

Два прохода, шаг за шагом

1. Запустите DFS по всему графу. Когда вершина завершает обработку (все её исходящие соседи обработаны), добавьте её в список.
2. Обратите все рёбра, чтобы получить транспонированный граф.
3. Пройдите по списку завершения с конца к началу. Для каждой ещё не посещённой вершины запустите DFS на транспонированном графе. Всё, что достигнет этот обход, — одна КСС.

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

Разобранный пример

Возьмём 8 вершин и такие рёбра:

0 → 1, 1 → 2, 2 → 0      (cycle A: 0, 1, 2)
2 → 3
3 → 4, 4 → 5, 5 → 3      (cycle B: 3, 4, 5)
6 → 5
6 → 7, 7 → 6             (cycle C: 6, 7)

КСС должны быть 2, 5 и 7.

Первый проход

Начните DFS с 0 и идите 0 → 1 → 2 → 3 → 4 → 5. Из вершины 5 некуда идти по новым вершинам, поэтому она завершается первой, затем 4, затем 3. Вернувшись в 2, идти некуда, поэтому завершаются 2, 1 и 0. Вершина 6 ещё не посещена, поэтому начните с неё: 5 уже обработана, поэтому идите в 7, которая завершается, затем 6. Порядок завершения такой:

5, 4, 3, 2, 1, 0, 7, 6

Второй проход

Обратите все рёбра и обрабатывайте вершины с конца этого списка: сначала 6. В обратном графе из 6 можно добраться только до 7, поэтому 7 — первая КСС. Следующая непосещённая — 0, из которой в обратном графе можно добраться до 2 и 1, что даёт 2. Ребро 2 → 3 теперь указывает 3 → 2, но 2 уже отнесена к компоненте, поэтому обход там останавливается. Наконец, из 3 можно добраться до 5 и 4, что даёт 5.

Почему это работает

Представьте граф КСС (каждая компонента сжата в одну вершину), в котором нет циклов. На первом проходе вершина, завершившаяся последней, всегда принадлежит «источниковой» компоненте — той, в которую нет рёбер из других неотнесённых компонент. Обращение рёбер превращает этот источник в сток, поэтому DFS, запущенный оттуда, не может выйти за пределы своей компоненты. После удаления этой компоненты те же рассуждения применимы к следующей.

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

Реализация на Python

Эта версия использует итеративный DFS, поэтому не упрётся в ограничение рекурсии Python на глубоких графах.

from collections import defaultdict

def kosaraju(n, edges):
    graph = defaultdict(list)
    reverse = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        reverse[v].append(u)

    # Pass 1: record vertices in the order they finish (iterative DFS)
    visited = [False] * n
    order = []
    for start in range(n):
        if visited[start]:
            continue
        visited[start] = True
        stack = [(start, iter(graph[start]))]
        while stack:
            node, neighbors = stack[-1]
            for nxt in neighbors:
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append((nxt, iter(graph[nxt])))
                    break
            else:
                stack.pop()
                order.append(node)

    # Pass 2: DFS on the reversed graph, latest finish time first
    visited = [False] * n
    components = []
    for start in reversed(order):
        if visited[start]:
            continue
        visited[start] = True
        component = []
        stack = [start]
        while stack:
            node = stack.pop()
            component.append(node)
            for nxt in reverse[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append(nxt)
        components.append(component)
    return components


edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 5), (6, 7), (7, 6)]
print(kosaraju(8, edges))  # [[6, 7], [0, 2, 1], [3, 5, 4]]

Порядок вершин внутри каждой компоненты зависит от обхода, поэтому в тестах сравнивайте компоненты как множества. Мы проверили эту реализацию против переборной проверки достижимости на 2 000 случайных графах.

Сложность

Память — O(V + E) для двух списков смежности плюс O(V) для массива посещённых, порядка завершения и стека.

Ошибки, которые всё ломают

Самая частая ошибка — записывать вершины, когда DFS впервые до них доходит, а не когда они завершают обработку. Другие: забыть обратить порядок завершения для второго прохода, запустить второй проход на исходном графе вместо обратного, не очистить массив посещённых между проходами и начинать только с вершины 0, из-за чего несвязные части пропускаются. Рекурсивный DFS также может переполнить стек на длинных цепочках — поэтому код выше итеративный.

Хорошие тесты: одна вершина, вершина с петлёй, один большой цикл, однонаправленная цепочка (каждая вершина — своя КСС), два цикла, соединённые одним ребром, и несвязный граф.

Косараджу против Тарьяна

Оба работают за O(V + E). Косараджу делает два прохода и строит обратный граф, что упрощает объяснение и снижает риск ошибки. Алгоритм Тарьяна делает всё за один проход без обратного графа, но отслеживает индексы обнаружения и low-link значения на стеке — больше состояния, которое нужно держать в голове. На собеседовании используйте тот, который вы можете корректно реализовать и объяснить. Если интервьюер просит один проход — это намёк на Тарьяна.

Практика на задачах с графами

Один раз пройдите пример выше вручную, прежде чем писать код; большинство ошибок проявляются как неверный порядок завершения. Похожие руководства: Флойд–Уоршелл для кратчайших путей между всеми парами, Беллман–Форд для графов с отрицательными рёбрами и наша шпаргалка по Big O. Если вы используете YesToTheOffer в практике программирования, его помощь по коду на скриншотах может проверить ваш подход, а транскрипт сессии покажет, насколько ясно вы объяснили свои рассуждения.