Топологическая сортировка графа: алгоритм Кана и поиск цикла

Зачем нужна топологическая сортировка графа?

Представьте, что вы собираете проект: сначала нужно скомпилировать модуль A, потом B, который от него зависит. Если зависимости образуют цикл — например, A требует B, а B требует A — собрать проект невозможно. В этой статье вы реализуете на Python топологическую сортировку графа с помощью алгоритма Кана и научитесь не только обнаруживать циклы, но и показывать конкретную циклическую цепочку. Это пригодится и на собеседованиях, и в реальных build-системах.

Подготовка: контракт графа

Граф зависимостей представим словарём, где ключ — задача, а значение — множество задач, от которых она зависит. Например:

graph = {
    "bundle": {"typecheck"},
    "typecheck": {"parse"},
    "parse": set(),
}

Ребро parse → typecheck означает, что parse должна выполниться первой. Если зависимость упомянута только в множестве, её всё равно нужно добавить как узел. Функция normalize приводит граф к единому виду:

def normalize(graph):
    nodes = set(graph)
    for deps in graph.values():
        nodes.update(deps)
    return {node: set(graph.get(node, set())) for node in nodes}

Алгоритм Кана: топологический порядок для DAG

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

from collections import deque

def topological_order(graph):
    dependencies = normalize(graph)
    # Строим обратные рёбра: для каждого узла список тех, кто от него зависит
    dependents = {node: set() for node in dependencies}
    for node, prereqs in dependencies.items():
        for prereq in prereqs:
            dependents[prereq].add(node)
    # Узлы без предшественников готовы к выполнению
    ready = deque(sorted(node for node, prereqs in dependencies.items() if not prereqs))
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for dependent in sorted(dependents[node]):
            dependencies[dependent].remove(node)
            if not dependencies[dependent]:
                ready.append(dependent)
    remaining = {node for node, deps in dependencies.items() if deps}
    if remaining:
        return None, remaining
    return order, set()

Проверим на ацикличном графе:

graph = {
    "bundle": {"typecheck"},
    "typecheck": {"parse"},
    "parse": set(),
    "test": {"typecheck"},
}
print(topological_order(graph))

Ожидаемый вывод (порядок может варьироваться из-за сортировки готовых узлов):

(['parse', 'typecheck', 'bundle', 'test'], set())

Почему частичного результата недостаточно

Внесём цикл:

cyclic = {
    "parse": {"bundle"},
    "typecheck": {"parse"},
    "bundle": {"typecheck"},
}
print(topological_order(cyclic))

Результат:

(None, {'parse', 'typecheck', 'bundle'})

Множество remaining включает все узлы, которые не удалось упорядочить, но оно не показывает конкретный цикл. Для этого нужен второй проход.

Поиск цикла через DFS

Глубинный поиск с тремя состояниями: "unseen" (не посещён), "active" (в текущем пути), "done" (обработан). Ребро в active узел — обратное, оно замыкает цикл.

def find_cycle(graph, candidates=None):
    graph = normalize(graph)
    allowed = set(graph) if candidates is None else set(candidates)
    state = {node: "unseen" for node in graph}
    stack = []
    position = {}

    def visit(node):
        state[node] = "active"
        position[node] = len(stack)
        stack.append(node)
        for dep in sorted(graph[node]):
            if dep not in allowed:
                continue
            if state[dep] == "unseen":
                cycle = visit(dep)
                if cycle:
                    return cycle
            elif state[dep] == "active":
                start = position[dep]
                return stack[start:] + [dep]
        stack.pop()
        position.pop(node)
        state[node] = "done"
        return None

    for node in sorted(allowed):
        if state[node] == "unseen":
            cycle = visit(node)
            if cycle:
                return cycle
    return None

Объединение этапов

Функция schedule возвращает либо порядок, либо найденный цикл:

def schedule(graph):
    order, remaining = topological_order(graph)
    if order is not None:
        return {"order": order, "cycle": None}
    return {"order": None, "cycle": find_cycle(graph, remaining)}

print(schedule(cyclic))

Ожидаемый вывод:

{'order': None, 'cycle': ['bundle', 'typecheck', 'parse', 'bundle']}

Цикл представлен списком, где последний элемент равен первому, а каждая соседняя пара — реальная зависимость.

Тесты для проверки

Напишем функции, проверяющие корректность порядка и цикла:

def assert_valid_order(graph, order):
    index = {node: i for i, node in enumerate(order)}
    normalized = normalize(graph)
    assert set(order) == set(normalized)
    for node, deps in normalized.items():
        for dep in deps:
            assert index[dep] < index[node]

def assert_valid_cycle(graph, cycle):
    normalized = normalize(graph)
    assert cycle[0] == cycle[-1]
    for node, dep in zip(cycle, cycle[1:]):
        assert dep in normalized[node]

# Тест ацикличного графа
order, remaining = topological_order(graph)
assert not remaining
assert_valid_order(graph, order)

# Тест циклического графа
result = schedule(cyclic)
assert result["order"] is None
assert_valid_cycle(cyclic, result["cycle"])

Добавим краевые случаи:

# Самозацикливание
assert_valid_cycle({"a": {"a"}}, schedule({"a": {"a"}})["cycle"])

# Цикл + зависимый узел
blocked = {"a": {"b"}, "b": {"a"}, "deploy": {"a"}}
assert_valid_cycle(blocked, schedule(blocked)["cycle"])

# Ацикличная компонента + цикл
mixed = {"lint": set(), "a": {"b"}, "b": {"a"}}
assert_valid_cycle(mixed, schedule(mixed)["cycle"])

Сложность и ограничения

Оба прохода работают за O(V + E), если не учитывать сортировку (она добавляет O(V log V) для детерминизма). Рекурсивный DFS может превысить лимит глубины на очень больших графах; для продакшена лучше использовать итеративный стек. Алгоритм предполагает статические зависимости и не учитывает ресурсы — в реальных build-системах нужны кэширование, параллелизм и обработка ошибок.

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

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

Практический вывод

Прямо сейчас откройте редактор и реализуйте топологическую сортировку графа с поиском цикла по шаблону из статьи. Протестируйте на своих примерах — например, на зависимостях модулей в проекте. Это укрепит понимание алгоритмов на графах и подготовит к задачам на собеседованиях.