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

Коротко

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

В ориентированном графе вершины u и v сильно связаны, если из u достижима v и из v достижима u.

Компонента сильной связности (КСС) — максимальное множество попарно сильно связанных вершин.

    1 → 2 → 3 → 4
    ↑   ↓       ↓
    ←── 5       6 ⇄ 7

КСС: {1, 2, 5}, {3}, {4}, {6, 7}

Из вершины 1 можно дойти до 2, из 2 через 5 обратно в 1 — они в одной компоненте. А вершина 3 сама по себе: обратного пути из неё нет.

Зачем это нужно на практике:

• анализ зависимостей — циклические импорты в модулях образуют КСС;
• 2-SAT — задача сводится к проверке, лежат ли переменная и её отрицание в одной КСС;
• социальные графы — взаимно связанные группы;
• веб-граф — кластеры взаимно ссылающихся страниц;
• упрощение графа — сжатие каждой КСС в вершину даёт ациклический граф.

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

Косарайю строится на двух наблюдениях.

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

Второе. Транспонирование графа (разворот всех рёбер) не меняет состав компонент. Если из u в v и обратно были пути, после разворота они тоже есть, только направления поменялись.

Отсюда алгоритм в три шага:

1. Обход в глубину исходного графа, запоминая вершины в порядке завершения обработки.
2. Транспонировать граф.
3. Обходить транспонированный граф в порядке, обратном порядку завершения. Каждый обход выделяет ровно одну компоненту.

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

Ключевой момент — порядок из первого прохода.

Вершина, завершившаяся последней, лежит в компоненте, которая в конденсации является истоком (в неё не входят рёбра из других компонент).

После транспонирования этот исток становится стоком. Значит обход из неё не сможет «убежать» в другие компоненты — он охватит ровно её КСС и остановится.

Дальше повторяем для следующей незатронутой вершины по списку.

Реализация

def kosaraju(graph: dict) -> list[list]:
    visited = set()
    order = []

    # 1. порядок завершения (итеративно, чтобы не упереться в стек)
    def dfs_order(start):
        stack = [(start, iter(graph.get(start, ())))]
        visited.add(start)

        while stack:
            node, it = stack[-1]
            advanced = False
            for nxt in it:
                if nxt not in visited:
                    visited.add(nxt)
                    stack.append((nxt, iter(graph.get(nxt, ()))))
                    advanced = True
                    break
            if not advanced:
                order.append(node)      # вершина завершена
                stack.pop()

    for v in graph:
        if v not in visited:
            dfs_order(v)

    # 2. транспонируем граф
    transposed = {v: [] for v in graph}
    for v in graph:
        for u in graph[v]:
            transposed.setdefault(u, []).append(v)

    # 3. обход в обратном порядке завершения
    visited.clear()
    components = []

    for v in reversed(order):
        if v in visited:
            continue

        component = []
        stack = [v]
        visited.add(v)

        while stack:
            node = stack.pop()
            component.append(node)
            for nxt in transposed.get(node, ()):
                if nxt not in visited:
                    visited.add(nxt)
                    stack.append(nxt)

        components.append(sorted(component))

    return components


graph = {
    1: [2],
    2: [3, 5],
    3: [4],
    4: [6],
    5: [1],
    6: [7],
    7: [6],
}

for comp in kosaraju(graph):
    print(comp)
# [1, 2, 5]
# [3]
# [4]
# [6, 7]

Конденсация графа

Часто нужен не просто список компонент, а сжатый ациклический граф. Он позволяет применять к исходной задаче алгоритмы для ациклических графов — топологическую сортировку, динамическое программирование.

def condensation(graph: dict):
    components = kosaraju(graph)

    # вершина -> номер её компоненты
    comp_id = {}
    for i, comp in enumerate(components):
        for v in comp:
            comp_id[v] = i

    condensed = {i: set() for i in range(len(components))}
    for v in graph:
        for u in graph[v]:
            if comp_id[v] != comp_id[u]:
                condensed[comp_id[v]].add(comp_id[u])

    return components, {k: sorted(v) for k, v in condensed.items()}


comps, cond = condensation(graph)
print(comps)   # [[1, 2, 5], [3], [4], [6, 7]]
print(cond)    # {0: [1], 1: [2], 2: [3], 3: []}

Полученный граф гарантированно ациклический — это можно использовать как проверку корректности.

Косарайю или Тарьян

Обе задачи решают за O(V + E), выбор по вкусу и обстоятельствам.

Практически: Тарьян эффективнее, но Косарайю проще понять и написать без ошибок. На собеседовании достаточно знать оба и уметь объяснить разницу.

Полезная деталь: Тарьян выдаёт компоненты сразу в порядке, обратном топологическому в конденсации, — это иногда экономит отдельную сортировку.

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

Обход в прямом порядке вместо обратного. Алгоритм выдаст неверные компоненты. Порядок принципиален.

Порядок входа вместо порядка завершения. Тоже сломает результат — нужно именно время окончания обработки вершины.

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

Рекурсивный обход на больших графах. Глубина может достигать числа вершин — Python упадёт. В коде намеренно итеративная версия.

Что запомнить

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

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→