Топологическая сортировка 🧭

Каждый раз, когда ты запускаешь loss.backward() в PyTorch или обучаешь модель в TensorFlow, внутри фреймворка происходит нечто гораздо более структурированное, чем просто «вычислить формулу». Любая нейросеть — это не одна большая формула, а вычислительный граф (computational graph): множество элементарных операций (сложение, умножение, матричное произведение, применение функции активации), связанных друг с другом отношением «результат одной операции — вход для другой». Этот граф направленный — стрелка идёт от операции-источника к операции-потребителю, — и ациклический: результат операции никогда не может зависеть сам от себя. Другими словами, вычислительный граф нейросети — это ориентированный ациклический граф, DAG, и именно такой граф — главный герой этого урока.

Прежде чем фреймворк сможет выполнить forward pass — вычислить выход сети по входным данным, — он должен решить простую, но принципиальную задачу: в каком порядке выполнять операции узлов графа? Нельзя вычислить сумму двух чисел раньше, чем вычислены оба слагаемых; нельзя применить функцию активации к результату линейного слоя раньше, чем вычислен сам этот результат. Порядок, в котором выполняются узлы графа, обязан уважать все стрелки зависимостей — и именно такой порядок называется топологической сортировкой. Без неё «выполнить граф» было бы попросту невозможно определить однозначно.

Ещё интереснее происходит на этапе backward pass — обратного распространения ошибки. Чтобы вычислить градиент функции потерь по весам, нужно пройти граф в направлении, обратном forward pass: сначала вычислить градиент по выходу сети, затем передать его «назад» через каждую операцию к её входам — но только тогда, когда градиенты уже известны от абсолютно всех узлов, которые эту операцию потребляли. Это правило — «нельзя вычислить градиент узла, пока не готовы градиенты всех его потребителей» — есть не что иное, как топологическая сортировка того же графа, только пройденная в обратном порядке. Автоматическое дифференцирование (autograd в PyTorch, граф исполнения в TensorFlow) в буквальном смысле реализовано поверх алгоритмов, которые ты изучишь в этом уроке.

Тема выходит далеко за пределы нейросетей. Каждый раз, когда pip устанавливает пакеты в правильном порядке, компилятор собирает модули в порядке их зависимостей, а планировщик задач вроде Apache Airflow решает, какой шаг пайплайна данных запустить следующим, — все они решают ровно одну и ту же задачу: дан набор элементов с отношениями «это должно случиться раньше того», нужно построить порядок, который эти отношения не нарушает. В этом уроке ты разберёшься, что такое топологическая сортировка формально, почему она возможна только для DAG, освоишь два классических алгоритма её построения — через обход в глубину и через алгоритм Кана с подсчётом входящих степеней, — а также увидишь, как невозможность построить такой порядок автоматически вскрывает циклы в графе, будь то циклическая зависимость пакетов или ошибочно построенный граф вычислений.

История

Первое формальное и широко цитируемое описание алгоритма топологической сортировки принадлежит Артуру Кану (Arthur B. Kahn), опубликовавшему в 1962 году в журнале Communications of the ACM статью с говорящим названием «Topological sorting of large networks» — «Топологическая сортировка больших сетей». Контекст статьи был предельно практическим: к началу 1960-х годов в промышленности и оборонных проектах США уже активно использовались методы сетевого планирования — PERT (Program Evaluation and Review Technique) и метод критического пути (Critical Path Method, CPM), разработанные чуть раньше, в конце 1950-х, для планирования крупных инженерных проектов вроде разработки баллистических ракет подводных лодок «Поларис». Эти методы требовали представлять проект как сеть задач с отношениями предшествования — одна задача не может начаться, пока не завершены другие, — и Кан предложил универсальный, эффективный алгоритм, который приводит такую сеть к линейному порядку выполнения, работающий даже на сетях с огромным числом узлов, для которых ручное планирование было немыслимо.

Второй классический подход — через обход в глубину — оформился чуть позже, в середине 1970-х годов, во многом благодаря работам Роберта Тарьяна (Robert Tarjan), одного из самых влиятельных исследователей алгоритмов на графах XX века. Тарьян показал, что глубинный обход графа — тот самый, что ты изучил в прошлом уроке, — сам по себе, почти бесплатно, даёт топологический порядок в качестве побочного продукта: достаточно запоминать порядок, в котором обход «выходит» из вершин (завершает их обработку), и развернуть этот порядок задним числом. Это не совпадение: тот же принцип «времени выхода» из вершины при DFS лежит и в основе алгоритма Тарьяна для поиска компонент сильной связности, опубликованного годом ранее, в 1972 году, — топологическая сортировка через DFS оказалась естественным родственником более общих идей о структуре ориентированных графов.

Практическая ценность идеи проявилась в информатике почти сразу же, причём в очень приземлённой форме. Классическая утилита make, созданная Стюартом Фелдманом (Stuart Feldman) в Bell Labs в 1976 году, стала первым по-настоящему массовым инструментом, в котором задача сборки программы из множества файлов с перекрёстными зависимостями решалась именно через построение и обход графа зависимостей — по сути, через ту же топологическую сортировку, пусть и без явного упоминания этого термина в документации make. Полвека спустя тот же принцип лежит в основе куда более современных инструментов: система оркестрации задач Apache Airflow называет свой центральный объект прямо в честь этой структуры — класс, которым описывается пайплайн обработки данных, называется именно DAG, и одна из первых проверок, которую Airflow выполняет при загрузке описания пайплайна, — это попытка построить топологический порядок задач, чтобы убедиться, что в графе зависимостей нет циклов.

Определение: топологический порядок и почему нужен именно DAG

Интуиция

Представь список дел на утро с внутренними зависимостями: нельзя надеть ботинки раньше носков, нельзя выйти из дома раньше, чем оделся, но при этом совершенно неважно, в каком порядке почистить зубы и сварить кофе — эти два действия друг от друга не зависят. Топологическая сортировка — это ровно то, что ты интуитивно делаешь, планируя такое утро: ты строишь одну общую последовательность действий, которая уважает все жёсткие ограничения «сначала это, потом то», а там, где ограничений нет, — заполняет порядок произвольно, любым способом, не нарушающим остальные правила.

Формально эта интуиция переносится на граф: вершины — это «дела» или «события», а направленное ребро $u \to v$ значит «$u$ должно случиться раньше $v$». Топологическая сортировка — это способ разложить все вершины графа в один ряд так, чтобы для каждой такой стрелки её начало оказалось в этом ряду левее конца.

Формальное определение

Определение. Топологической сортировкой ориентированного графа $G = (V, E)$ называется такой линейный порядок его вершин $v_1, v_2, \ldots, v_n$, что для каждого ориентированного ребра $(u, v) \in E$ вершина $u$ предшествует вершине $v$ в этом порядке. Топологическая сортировка графа $G$ существует тогда и только тогда, когда $G$ является ориентированным ациклическим графом (Directed Acyclic Graph, DAG) — направленным графом, не содержащим ни одного ориентированного цикла.

Почему наличие цикла делает задачу неразрешимой, легко увидеть напрямую из определения. Пусть в графе есть цикл $u_1 \to u_2 \to \cdots \to u_k \to u_1$. Если бы топологический порядок существовал, то из ребра $u_1 \to u_2$ следовало бы, что $u_1$ стоит раньше $u_2$; из ребра $u_2 \to u_3$ — что $u_2$ раньше $u_3$; и так далее по цепочке, вплоть до последнего ребра $u_k \to u_1$, которое требует, чтобы $u_k$ стоял раньше $u_1$. Собирая все эти требования вместе, получаем: $u_1$ раньше $u_2$ раньше … раньше $u_k$ раньше $u_1$ — вершина должна предшествовать сама себе, что абсурдно для линейного порядка. Значит, ни одна расстановка вершин в ряд не может одновременно удовлетворить все рёбра цикла — топологического порядка для такого графа не существует в принципе, а не просто «трудно найти».

Важно сразу отметить и вторую особенность определения: топологический порядок, как правило, не единственный. Если в графе есть две вершины, между которыми нет ни прямого, ни косвенного пути (ни один путь не связывает их зависимостью), их можно расставить в любом относительном порядке — оба варианта будут одинаково корректными топологическими сортировками одного и того же графа.

Примеры с разбором

Пример 1. Одевание утром. Граф зависимостей: носки → ботинки, футболка → куртка, ботинки и куртка независимы друг от друга.

graph = {
    "носки": ["ботинки"],
    "ботинки": [],
    "футболка": ["куртка"],
    "куртка": [],
}

Оба варианта — [носки, ботинки, футболка, куртка] и [футболка, куртка, носки, ботинки] и, например, [носки, футболка, ботинки, куртка] — являются корректными топологическими порядками: во всех них носки стоят раньше ботинок, а футболка раньше куртки, и это единственное, что требуется. Ни один из вариантов не «более правильный», чем другие.

Пример 2. Граф университетских курсов. Пусть зависимости такие: Алгебра → Матанализ, Алгебра → Геометрия, Матанализ → Топология, Матанализ → Диффуры, Геометрия → Топология (Топология требует и Матанализа, и Геометрии).

graph = {
    "Алгебра": ["Матанализ", "Геометрия"],
    "Геометрия": ["Топология"],
    "Матанализ": ["Топология", "Диффуры"],
    "Топология": [],
    "Диффуры": [],
}

Здесь у графа тоже несколько допустимых порядков: и «Алгебра, Геометрия, Матанализ, Диффуры, Топология», и «Алгебра, Матанализ, Геометрия, Диффуры, Топология» одинаково корректны — единственное жёсткое требование в том, что Алгебра стоит раньше обоих своих «потомков», а Топология — позже обоих своих «родителей». Этот граф мы будем использовать как сквозной пример дальше в уроке, разбирая на нём оба алгоритма построения порядка.

Пример 3. Вычислительный граф $f = (a + b) \cdot c$. Узлы: $a$, $b$, $c$ — входные значения (у них нет входящих рёбер, они ничего не «наследуют»); $\mathrm{add} = a + b$ — узел сложения, зависящий от $a$ и $b$; $\mathrm{mul} = \mathrm{add} \cdot c$ — узел умножения, зависящий от $\mathrm{add}$ и $c$ и являющийся итоговым выходом $f$.

graph = {
    "a": ["add"],
    "b": ["add"],
    "c": ["mul"],
    "add": ["mul"],
    "mul": [],
}

Любой валидный топологический порядок этого графа — например, $a, b, c, \mathrm{add}, \mathrm{mul}$ — это в точности допустимый порядок выполнения операций при forward pass: узел $\mathrm{add}$ нельзя вычислить раньше $a$ и $b$, узел $\mathrm{mul}$ нельзя вычислить раньше $\mathrm{add}$ и $c$. При этом порядок между $a$, $b$ и $c$ не важен — их можно вычислять в любой последовательности или даже параллельно, поскольку между ними самими нет ребра зависимости. Этот граф мы тоже будем использовать сквозным примером — на нём же ниже разберём, как строится обратный порядок для backward pass.

Почему это важно

Требование «только DAG» — не техническая деталь, а прямое следствие смысла самой задачи, и оно проявляется в реальных системах абсолютно буквально. Если попытаться создать зацикленный вычислительный граф в TensorFlow в режиме статического графа, построение графа завершится ошибкой валидации ещё до всякого выполнения; в описании пайплайна Apache Airflow циклическая зависимость задач ловится специальным исключением AirflowDagCycleException именно потому, что валидатор Airflow пытается построить топологический порядок задач и не может этого сделать. Понимание того, что топологическая сортировка возможна только для DAG, — это понимание того, почему «зацикленная» спецификация задач, курсов или вычислений — это не сложная, а логически неразрешимая постановка, которую нужно чинить на уровне самих зависимостей, а не пытаться «обойти» более умным алгоритмом.

Алгоритм через обход в глубину

Интуиция

Идея DFS-подхода обманчиво проста: чтобы правильно поставить вершину в итоговый порядок, нужно сначала полностью разобраться со всем, что из неё «растёт» — со всеми вершинами, достижимыми из неё по исходящим рёбрам, — и только после этого «закрыть» саму вершину. Представь себе, что ты собираешь программу из модулей: прежде чем сказать «модуль A готов», нужно, чтобы были полностью собраны все модули, от которых A зависит напрямую или косвенно. DFS естественно реализует именно эту логику: обход уходит вглубь по цепочке зависимостей, и вершина помечается «завершённой» только в момент выхода из рекурсии — когда все её потомки уже обработаны.

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

Формальное определение алгоритма

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

def topological_sort_dfs(graph):
    visited = set()
    order = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        order.append(node)  # добавляем ПОСЛЕ обработки всех потомков

    for node in graph:
        if node not in visited:
            dfs(node)

    return order[::-1]

Примеры с разбором

Пример 1. Простая цепочка. Граф {"A": ["B"], "B": ["C"], "C": []}. Обход начинается с A: dfs("A") помечает A посещённой, идёт в единственного соседа B; dfs("B") помечает B, идёт в C; dfs("C") помечает C, у неё нет соседей — C сразу добавляется в order: order = ["C"]. Возврат в вызов для B: соседи обработаны, B добавляется: order = ["C", "B"]. Возврат в вызов для A: A добавляется: order = ["C", "B", "A"]. После разворота: ["A", "B", "C"] — ровно ожидаемый порядок для простой цепочки зависимостей.

Пример 2. Граф университетских курсов. Возьмём граф из примера 2 предыдущего раздела, с порядком перебора вершин в главном цикле «Алгебра, Геометрия, Матанализ, Топология, Диффуры» (именно в таком порядке они идут в Python-словаре). dfs("Алгебра") идёт в первого соседа "Матанализ": dfs("Матанализ") идёт в "Топология": dfs("Топология") — соседей нет, добавляем: order = ["Топология"]. Возврат в "Матанализ", идём во второго соседа "Диффуры": соседей нет, добавляем: order = ["Топология", "Диффуры"]. Возврат в "Матанализ" — соседи обработаны, добавляем: order = ["Топология", "Диффуры", "Матанализ"]. Возврат в "Алгебра", идём во второго соседа "Геометрия": единственный сосед "Топология" уже посещён — пропускаем, добавляем саму "Геометрию": order = ["Топология", "Диффуры", "Матанализ", "Геометрия"]. Возврат в "Алгебра" — оба соседа обработаны, добавляем: order = ["Топология", "Диффуры", "Матанализ", "Геометрия", "Алгебра"]. Главный цикл проверяет оставшиеся вершины — все уже посещены. После разворота: ["Алгебра", "Геометрия", "Матанализ", "Диффуры", "Топология"]. Проверка по рёбрам: Алгебра раньше Матанализа и Геометрии — да; Матанализ раньше Топологии и Диффуров — да; Геометрия раньше Топологии — да. Порядок корректен — и обрати внимание, что он отличается от того, что даст алгоритм Кана на этом же графе (см. следующий раздел), что снова подтверждает: единственно верного порядка не существует, существует лишь множество одинаково корректных.

Пример 3. Вычислительный граф $f = (a+b)\cdot c$. С перебором вершин в порядке "a", "b", "c", "add", "mul". dfs("a") идёт в "add": dfs("add") идёт в "mul": dfs("mul") — соседей нет, добавляем: order = ["mul"]. Возврат в "add" — соседи обработаны, добавляем: order = ["mul", "add"]. Возврат в "a", добавляем: order = ["mul", "add", "a"]. Главный цикл переходит к "b": не посещена, dfs("b") — единственный сосед "add" уже посещён, добавляем саму "b": order = ["mul", "add", "a", "b"]. Переходим к "c": не посещена, dfs("c") — единственный сосед "mul" уже посещён, добавляем "c": order = ["mul", "add", "a", "b", "c"]. После разворота: ["c", "b", "a", "add", "mul"]. Это тоже корректный порядок выполнения forward pass — проверь сам по рёбрам: $a$ и $b$ стоят раньше $\mathrm{add}$, а $c$ и $\mathrm{add}$ — раньше $\mathrm{mul}$, все условия соблюдены, хотя порядок среди $a$, $b$, $c$ получился иным, чем в примере из предыдущего раздела.

Почему это важно

DFS-подход к топологической сортировке имеет ту же сложность $O(V + E)$, что и сам обход в глубину из прошлого урока, — никакой дополнительной асимптотической цены за построение порядка не платится, это буквально тот же обход с одной дополнительной операцией на каждый выход из рекурсии. Ровно поэтому топологическая сортировка через DFS так органично сочетается с другими алгоритмами на графах, построенными поверх глубинного обхода, — например, с поиском компонент сильной связности. Но у рекурсивной реализации есть и практическое ограничение, знакомое ещё по урокам о деревьях: на очень длинных цепочках зависимостей (граф, вырождающийся в почти линейную цепочку из десятков тысяч вершин) рекурсия может упереться в ограничение глубины стека вызовов Python — и здесь на помощь приходит либо итеративная версия DFS с явным стеком, либо второй алгоритм, к которому мы переходим дальше и который по своей природе целиком итеративен.

Алгоритм Кана: через подсчёт входящих степеней

Интуиция

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

Величина, которую алгоритм отслеживает для каждой вершины, называется входящей степенью (indegree) — числом рёбер, входящих в вершину. Вершина с входящей степенью $0$ — это вершина, у которой нет ни одной ещё не пройденной зависимости, а значит, её можно смело добавлять в результат прямо сейчас.

Формальное определение алгоритма

Определение. Алгоритм Кана строит топологический порядок так: 1) для каждой вершины графа вычисляется входящая степень $\mathrm{indegree}(v)$ — число входящих в неё рёбер; 2) все вершины с $\mathrm{indegree}(v) = 0$ помещаются в очередь; 3) пока очередь не пуста, из неё извлекается вершина $u$, добавляется в результат, и для каждого исходящего ребра $(u, w)$ значение $\mathrm{indegree}(w)$ уменьшается на единицу — если оно становится равным нулю, $w$ помещается в очередь; 4) когда очередь опустеет, результат — это искомый топологический порядок, если число обработанных вершин равно $|V|$.

from collections import deque

def topological_sort_kahn(graph):
    indegree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] = indegree.get(neighbor, 0) + 1

    queue = deque(node for node in indegree if indegree[node] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return order

Примеры с разбором

Пример 1. Граф университетских курсов. Тот же граф, что и в предыдущих разделах. Входящие степени: Алгебра — $0$, Геометрия — $1$ (от Алгебры), Матанализ — $1$ (от Алгебры), Диффуры — $1$ (от Матанализа), Топология — $2$ (от Матанализа и Геометрии). Начальная очередь: [Алгебра] — единственная вершина с нулевой входящей степенью. Обрабатываем Алгебру: результат ["Алгебра"]; у неё два исходящих ребра — в Матанализ (степень $1 \to 0$, добавляем в очередь) и в Геометрию (степень $1 \to 0$, добавляем в очередь); очередь [Матанализ, Геометрия]. Обрабатываем Матанализ: результат ["Алгебра", "Матанализ"]; исходящие рёбра — в Топологию (степень $2 \to 1$, ещё не ноль) и в Диффуры (степень $1 \to 0$, добавляем); очередь [Геометрия, Диффуры]. Обрабатываем Геометрию: результат [..., "Геометрия"]; ребро в Топологию (степень $1 \to 0$, добавляем); очередь [Диффуры, Топология]. Обрабатываем Диффуры (без исходящих рёбер), затем Топологию. Итоговый порядок: ["Алгебра", "Матанализ", "Геометрия", "Диффуры", "Топология"] — обрати внимание, что этот порядок отличается от того, что дал DFS-подход в предыдущем разделе (там Геометрия шла раньше Матанализа), хотя оба одинаково корректны.

Пример 2. Вычислительный граф $f=(a+b)\cdot c$ и понятие «слоёв». Входящие степени: $a$, $b$, $c$ — по $0$; $\mathrm{add}$ — $2$ (от $a$ и $b$); $\mathrm{mul}$ — $2$ (от $\mathrm{add}$ и $c$). Начальная очередь сразу содержит три вершины: [a, b, c]. Обрабатываем $a$: результат ["a"], степень $\mathrm{add}$ уменьшается до $1$ (ещё не ноль). Обрабатываем $b$: результат ["a","b"], степень $\mathrm{add}$ уменьшается до $0$, добавляем в очередь: [c, add]. Обрабатываем $c$: результат ["a","b","c"], степень $\mathrm{mul}$ уменьшается до $1$. Обрабатываем $\mathrm{add}$: результат ["a","b","c","add"], степень $\mathrm{mul}$ уменьшается до $0$, добавляем: [mul]. Обрабатываем $\mathrm{mul}$: финальный результат ["a","b","c","add","mul"]. Ключевое наблюдение: в самом начале в очереди одновременно оказались сразу три вершины — $a$, $b$, $c$ — потому что между ними самими нет ни одного ребра зависимости. Это не случайность, а системное свойство алгоритма Кана: все вершины, одновременно находящиеся в очереди на одном и том же шаге, образуют «слой» — множество задач, которые можно выполнять параллельно, поскольку они не зависят друг от друга. DFS-подход такую информацию о параллелизме не даёт напрямую — а алгоритм Кана предоставляет её бесплатно, просто по своей структуре выполнения.

Пример 3. Порядок установки пакетов. Пакет A зависит от B и C; пакет B зависит от D; пакет C зависит от D; пакет D ни от чего не зависит. В терминах рёбер «зависимость должна быть установлена раньше»: D → B, D → C, B → A, C → A.

graph = {
    "D": ["B", "C"],
    "B": ["A"],
    "C": ["A"],
    "A": [],
}

Входящие степени: D — $0$, B — $1$, C — $1$, A — $2$. Начальная очередь: [D]. Обрабатываем D: результат ["D"], степени B и C уменьшаются до $0$, очередь [B, C]. Обрабатываем B: результат ["D","B"], степень A уменьшается до $1$. Обрабатываем C: результат ["D","B","C"], степень A уменьшается до $0$, добавляем. Обрабатываем A: финальный результат ["D","B","C","A"]. Пакетный менеджер вроде pip или npm, столкнувшись с такой структурой зависимостей, установит D первым, затем сможет устанавливать B и C в любом порядке (или параллельно — они не зависят друг от друга), и лишь в конце — A.

Почему это важно

Алгоритм Кана — не просто альтернативный способ получить тот же результат, что и DFS-подход: он даёт принципиально дополнительную информацию о структуре зависимостей, а именно — разбиение графа на «слои» одновременно готовых к выполнению задач, как показал пример 2. Это ровно то, что нужно системам оркестрации вроде Apache Airflow или Dagster, когда они решают, какие задачи пайплайна можно безопасно запустить параллельно на разных исполнителях, а не строго друг за другом. Кроме того, алгоритм Кана по своей природе итеративен — он не использует рекурсию вообще, а значит, не подвержен ограничению глубины стека вызовов, которое может стать проблемой для DFS-подхода на очень длинных цепочках зависимостей.

Обнаружение цикла и практические применения

Интуиция

Оба алгоритма из предыдущих разделов молчаливо предполагали, что граф — DAG. Но что, если это не так? Оказывается, ни одному из алгоритмов не нужна отдельная, специальная проверка «есть ли цикл» перед запуском — оба обнаруживают его как естественный побочный эффект попытки построить порядок, который построить невозможно. Если задача не имеет решения, сам процесс поиска решения «застревает» — и это застревание можно поймать и превратить в диагностику: не просто «сортировка не удалась», а «вот эти конкретные вершины участвуют в цикле».

Формальное определение

Определение. В алгоритме Кана признак цикла — простое числовое условие: если после завершения работы алгоритма длина результирующего списка order меньше $|V|$, значит в графе есть хотя бы один цикл, а вершины, ни разу не попавшие в очередь (то есть их входящая степень так и не опустилась до нуля), участвуют в этом цикле или зависят исключительно от него. В DFS-подходе цикл обнаруживается через трёхцветную маркировку вершин: белый цвет — вершина ещё не посещена, серый — вершина находится в процессе обработки (то есть присутствует в текущем стеке рекурсии), чёрный — вершина и всё её поддерево обхода полностью обработаны. Если во время обхода встречается ребро, ведущее в серую вершину, — это обратное ребро (back edge), однозначный признак цикла, поскольку серая вершина является предком текущей вершины в дереве обхода.

def has_cycle_dfs(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def visit(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color.get(neighbor, WHITE) == GRAY:
                return True                 # обратное ребро — цикл
            if color.get(neighbor, WHITE) == WHITE and visit(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(visit(node) for node in graph if color[node] == WHITE)

Примеры с разбором

Пример 1. Полностью циклический граф курсов. Пусть кто-то ошибочно указал зависимости так: A → B, B → C, C → A. Входящие степени: A — $1$ (от C), B — $1$ (от A), C — $1$ (от B) — у каждой вершины входящая степень $1$, ни одна не равна нулю. Начальная очередь алгоритма Кана оказывается пустой ещё до первого шага, цикл while queue не выполняется вовсе, результат order = [], длина $0 < 3 = |V|$ — цикл обнаружен мгновенно, причём в него вовлечены все три вершины графа. Это самый явный случай: когда весь граф — один цикл, алгоритм даже не успевает начать работу.

Пример 2. Частичный цикл внутри большего графа. Граф {"A": ["B"], "B": ["C"], "C": ["B"]} — вершина A указывает на B, а B и C образуют цикл между собой (B → C → B). Входящие степени: A — $0$, B — $2$ (от A и от C), C — $1$ (от B). Начальная очередь: [A]. Обрабатываем A: результат ["A"], степень B уменьшается до $1$ — ещё не ноль, очередь становится пустой. Алгоритм завершается с результатом ["A"], длина $1 < 3$ — цикл обнаружен, и, что важно, вершины B и C, оставшиеся необработанными (их входящая степень так и не достигла нуля), — это ровно те вершины, что образуют проблемный цикл, а не весь граф целиком. То же самое покажет и DFS-подход: обход из A окрашивает A в серый, идёт в B (серый), идёт в C (серый), а у C единственный сосед — B, который в этот момент всё ещё серый (обработка B не завершена, потому что она ждёт возврата из рекурсивного вызова для C) — это и есть обнаруженное обратное ребро C → B.

Пример 3. Практические применения — от сборки пакетов до обратного распространения ошибки. Диагностика циклов через топологическую сортировку — рабочий инструмент нескольких классов реальных систем. Системы сборки (make) и пакетные менеджеры (pip, npm, cargo) строят граф зависимостей модулей или пакетов и, если он оказывается ациклическим, определяют по нему порядок компиляции или установки; если же обнаруживается цикл (пакет A требует более новую версию пакета B, а B, в свою очередь, требует более старую версию A), система сообщает об ошибке разрешения зависимостей — именно так возникает знакомое многим сообщение ResolutionImpossible у pip. Системы оркестрации пайплайнов данных, такие как Apache Airflow, Dagster и Kubeflow Pipelines, требуют, чтобы граф задач был DAG буквально по определению (не случайно основной объект Airflow называется именно DAG), и выполняют топологическую сортировку задач как при валидации пайплайна на этапе загрузки, так и при определении, какие задачи готовы к запуску прямо сейчас. Классическая формулировка «сколько семестров нужно, чтобы пройти все курсы с учётом пререквизитов» — это прямое применение «слоёв» алгоритма Кана, разобранных в предыдущем разделе.

Но самое прямое и глубокое применение — то, с которого начинался этот урок. Возьмём вычислительный граф $f = (a+b) \cdot c$ из предыдущих разделов и построим граф с обращёнными рёбрами — граф, по которому распространяется градиент при backward pass: каждое ребро исходного графа переворачивается, поскольку информация о градиенте течёт в направлении, противоположном направлению вычислений. Раз в исходном графе $a \to \mathrm{add}$, то в графе распространения градиента — $\mathrm{add} \to a$; аналогично $\mathrm{add} \to b$, $\mathrm{mul} \to c$ и $\mathrm{mul} \to \mathrm{add}$. Входящие степени в этом обращённом графе: $\mathrm{mul}$ — $0$ (это выход сети, с него градиент начинает распространяться), $\mathrm{add}$ — $1$ (от $\mathrm{mul}$), $c$ — $1$ (от $\mathrm{mul}$), $a$ — $1$ (от $\mathrm{add}$), $b$ — $1$ (от $\mathrm{add}$). Алгоритм Кана на этом графе даёт порядок: сначала $\mathrm{mul}$ (градиент по выходу известен сразу, обычно он равен $1$), затем $\mathrm{add}$ и $c$ (оба зависят только от градиента $\mathrm{mul}$, могут обрабатываться в любом порядке), и лишь затем $a$ и $b$ (оба ждут градиента, вычисленного в узле $\mathrm{add}$). Это в точности реализация правила цепочки (chain rule) в том порядке, в котором его выполняет autograd в PyTorch: градиент узла вычисляется только после того, как получены и просуммированы градиенты от всех узлов, которые этот узел потребляли, — что при формальной записи есть не что иное, как топологическая сортировка графа с обращёнными рёбрами.

Почему это важно

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

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Дан граф с рёбрами A→B, B→C, A→C. Найди любой корректный топологический порядок.

Задание 2. Вычисли входящую степень каждой вершины графа {"X": ["Y", "Z"], "Y": ["Z"], "Z": []}.

Задание 3. Верно ли утверждение «у каждого DAG существует ровно один топологический порядок»? Обоснуй ответ конкретным примером.

Задание 4. Дан граф с рёбрами A→B, B→C, C→A. Объясни, почему топологического порядка для него не существует.

Задание 5. Для графа {"P": ["Q"], "Q": ["R"], "R": []} выполни DFS-алгоритм вручную: укажи список order до разворота и итоговый результат после разворота.

Задание 6. Для того же графа {"P": ["Q"], "Q": ["R"], "R": []} выполни алгоритм Кана вручную: покажи состояние очереди на каждом шаге.

Задание 7. Граф состоит из двух независимых цепочек: A→B и C→D (между парами {A,B} и {C,D} рёбер нет). Сколько существует различных корректных топологических порядков этого графа?

Задание 8. Определена ли топологическая сортировка для неориентированного графа? Объясни, почему да или почему нет.

Задание 9. В DFS-подходе список order до разворота получился таким: ["D", "C", "B", "A"]. Какой будет итоговый топологический порядок?

Задание 10. В алгоритме Кана на одном из шагов в очереди одновременно оказались три вершины. Что это говорит об отношениях между этими тремя вершинами?

Средние (задания 11–20)

Задание 11. Для графа курсов {"Алгебра": ["Матанализ", "Геометрия"], "Геометрия": ["Топология"], "Матанализ": ["Топология", "Диффуры"], "Топология": [], "Диффуры": []} вычисли входящие степени всех вершин и выполни алгоритм Кана пошагово, указав состояния очереди.

Задание 12. Для того же графа курсов выполни DFS-алгоритм, начиная обход с вершины «Алгебра» и перебирая соседей в порядке, в котором они перечислены в списках. Укажи список order до разворота и итоговый результат.

Задание 13. Есть ли цикл в графе {"A": ["B"], "B": ["C"], "C": ["D"], "D": ["B"]}? Если да, назови вершины, которые в нём участвуют.

Задание 14. Вычислительный граф $z = (x \cdot y) + (x - y)$. Построй узлы и рёбра графа (узлы $x$, $y$ — входы; $\mathrm{mul}=x\cdot y$; $\mathrm{sub}=x-y$; $\mathrm{add}=\mathrm{mul}+\mathrm{sub}=z$), затем выполни алгоритм Кана и укажи итоговый порядок.

Задание 15. Для графа из предыдущего задания опиши, в каком порядке при backward pass будут вычисляться градиенты, и объясни эту логику через понятие входящей степени в графе с обращёнными рёбрами.

Задание 16. В графе с $6$ вершинами алгоритм Кана завершился, обработав только $4$ вершины. Что из этого можно заключить?

Задание 17. Пакет A зависит от B и C; пакет B зависит от D; пакет C зависит от D; пакет D ни от чего не зависит. Определи порядок установки и укажи, какие пакеты можно установить параллельно.

Задание 18. Объясни, используя трёхцветную маркировку вершин при DFS, почему обнаружение ребра в СЕРУЮ вершину означает цикл, а обнаружение ребра в ЧЁРНУЮ вершину — не означает.

Задание 19. Для графа из задания 17 распредели вершины по «слоям» (уровням, которые можно выполнять параллельно) в стиле алгоритма Кана.

Задание 20. Объясни, почему список order, который DFS-алгоритм строит ДО разворота, уже гарантированно является топологическим порядком в обратном направлении — то есть почему разворот этого списка вообще даёт корректный результат.

Продвинутые (задания 21–30)

Задание 21. Граф состоит из $n$ вершин и не содержит ни одного ребра. Сколько существует различных корректных топологических порядков?

Задание 22. Пайплайн Airflow состоит из задач: extract→transform, transform→load, extract→validate, validate→load. Определи порядок выполнения через алгоритм Кана и укажи, могут ли transform и validate выполняться параллельно.

Задание 23. Начинающий разработчик в PyTorch пишет b = c + a, переиспользуя имя b, которое раньше уже участвовало в построении c (например, c было вычислено как c = a + b). Код выглядит «циклическим» на уровне имён переменных. Объясни, почему вычислительный граф autograd от этого реального цикла не образует.

Задание 24. Граф из $100\,000$ вершин представляет собой одну длинную цепочку $V_1 \to V_2 \to \cdots \to V_{100000}$. Сравни практический риск применения рекурсивного DFS-алгоритма и итеративного алгоритма Кана на таком графе.

Задание 25. Опиши, как модифицировать алгоритм Кана, чтобы он находил лексикографически наименьший из всех корректных топологических порядков графа.

Задание 26. Опиши, как с помощью топологического порядка и динамического программирования найти длину критического пути (самого длинного пути) в DAG с весами на рёбрах.

Задание 27. Учебный комитет хочет узнать минимальное число семестров, за которое можно пройти все курсы с учётом пререквизитов. Объясни, как это число связано со «слоями» алгоритма Кана.

Задание 28. Обычное дерево (из урока про деревья) не является ориентированным графом само по себе. Объясни, при каком условии дерево превращается в DAG, и приведи пример топологического порядка для дерева с корнем R и детьми A, B (рёбра направлены от родителя к ребёнку).

Задание 29. В компиляторах графов (например, в XLA или TVM) оптимизирующие проходы могут сливать (fuse) несколько операций графа в одну. Объясни, почему топологическая сортировка графа должна выполняться раньше таких проходов оптимизации, а не после них.

Задание 30. Опиши идею модификации DFS-алгоритма обнаружения цикла, которая возвращает не просто факт «цикл есть», а конкретный список вершин, образующих один найденный цикл.

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

❌ Ошибка: Считать, что топологическую сортировку можно применить к любому графу, включая графы с циклами или неориентированные графы.

✅ Правильно: Топологическая сортировка определена исключительно для ориентированных ациклических графов (DAG); для графа с циклом или для неориентированного графа задача не имеет решения в принципе.

💡 Почему: Само определение порядка опирается на направленность рёбер и на отсутствие противоречивых требований «$u$ раньше $v$ и $v$ раньше $u$ одновременно», что цикл создаёт по построению.

❌ Ошибка: Полагать, что у DAG существует ровно один правильный топологический порядок, и удивляться, когда два разных алгоритма (DFS и Кана) дают разные результаты на одном и том же графе.

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

💡 Почему: Определение требует лишь уважения к рёбрам графа, а не к какому-то дополнительному, неявному критерию «единственно правильного» порядка.

❌ Ошибка: В DFS-реализации добавлять вершину в результат в момент первого попадания в неё (на входе в рекурсию), а не на выходе.

✅ Правильно: Вершина должна добавляться в список order строго после того, как обработаны все её потомки, то есть на выходе из рекурсивного вызова, а список — развёрнут в конце.

💡 Почему: Добавление на входе не гарантирует, что все зависимые от вершины узлы уже обработаны, — итоговый порядок в этом случае может напрямую нарушать требования части рёбер.

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

✅ Правильно: В алгоритме Кана в очередь на старте попадают только вершины с нулевой ВХОДЯЩЕЙ степенью — число исходящих рёбер на готовность вершины к обработке никак не влияет.

💡 Почему: Вершина без входящих зависимостей может иметь сколько угодно исходящих рёбер — это не мешает ей быть готовой к обработке первой, а перепутанное направление подсчёта сразу даёт неверный начальный набор вершин.

❌ Ошибка: Запускать алгоритм Кана или DFS-алгоритм на графе и молча использовать результат, не проверив, обработаны ли все вершины (для Кана) или не встретилось ли обратное ребро (для DFS).

✅ Правильно: Всегда проверять len(order) == len(graph) для алгоритма Кана или явно использовать трёхцветную проверку в DFS-подходе — иначе на графе с циклом код молча вернёт неполный или некорректный порядок без единой ошибки.

💡 Почему: Без такой проверки баг проявится не сразу, а где-то дальше по пайплайну — например, в виде пропавших задач в системе планирования, — и искать причину придётся уже не там, где она возникла.

❌ Ошибка: Думать, что порядок вычисления градиентов при backward pass совпадает с порядком вычисления операций при forward pass.

✅ Правильно: Backward pass идёт в порядке, обратном топологической сортировке исходного графа (точнее — в порядке топологической сортировки графа с обращёнными рёбрами), а не в том же самом порядке, что и forward pass.

💡 Почему: Градиент узла можно вычислить только после того, как известны градиенты всех узлов, которые ЕГО использовали как вход, — а это по построению противоположное условие тому, что требуется для forward pass.

Главное запомнить

✅ Топологическая сортировка графа $G=(V,E)$ — линейный порядок вершин, в котором для каждого ребра $(u,v)\in E$ вершина $u$ стоит раньше $v$

✅ Такой порядок существует тогда и только тогда, когда граф — ориентированный ациклический граф (DAG); цикл делает задачу неразрешимой по построению, а не просто «сложной»

✅ Топологический порядок графа, как правило, не единственный — совпадение или несовпадение результатов разных алгоритмов не означает ошибку

✅ DFS-алгоритм: вершина добавляется в результат на выходе из рекурсии (после всех потомков), затем список разворачивается; сложность $O(V+E)$, совпадает с обычным обходом в глубину

✅ Алгоритм Кана: вершины с входящей степенью $0$ помещаются в очередь и последовательно обрабатываются, уменьшая входящую степень соседей; тоже $O(V+E)$, но полностью итеративен, без рекурсии

✅ Вершины, одновременно оказавшиеся в очереди алгоритма Кана на одном шаге, образуют «слой» — множество задач без взаимных зависимостей, которые можно выполнять параллельно

✅ Обнаружение цикла — естественный побочный эффект обоих алгоритмов: для Кана — если обработано меньше вершин, чем всего в графе; для DFS — обратное ребро в серую (ещё обрабатываемую) вершину

✅ Вычислительный граф нейросети — это DAG: топологический порядок определяет допустимую последовательность операций при forward pass

✅ Backward pass (backpropagation) — это топологическая сортировка графа с обращёнными рёбрами: градиент узла вычисляется только после получения градиентов от всех узлов, которые его использовали

✅ Практические применения выходят далеко за пределы учебных примеров: сборка проектов (make), разрешение зависимостей пакетов (pip, npm), оркестрация пайплайнов данных (Airflow, Dagster), автоматическое дифференцирование (PyTorch, TensorFlow)

Связь с темами курса

🔙 Откуда пришли: Из урока 261 — обход графов в глубину (DFS) и в ширину (BFS). DFS-подход к топологической сортировке — это буквально тот же обход, дополненный одним правилом (добавлять вершину на выходе из рекурсии) и финальным разворотом результата; без понимания механики DFS из прошлого урока разобраться, почему это вообще работает, было бы гораздо сложнее.

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

🎯 В машинном обучении: Это, пожалуй, самая прямая и постоянно используемая связь во всём алгоритмическом блоке курса. Каждый вычислительный граф нейросети — от однослойного перцептрона до трансформера с миллиардами параметров — это DAG операций, и именно топологическая сортировка определяет, в каком порядке эти операции могут быть выполнены корректно при forward pass, и в каком обратном порядке — при вычислении градиентов на backward pass. Автоматическое дифференцирование в PyTorch и TensorFlow — это, по сути, инженерная надстройка над алгоритмами этого урока: динамический граф autograd в PyTorch строится заново при каждом forward pass именно потому, что для вычисления градиентов ему нужен корректный (обращённый) топологический порядок, а граф, который не является DAG, автоматическое дифференцирование корректно обработать не может в принципе.

Интересные факты

📌 Статья Артура Кана 1962 года, впервые формально описавшая алгоритм топологической сортировки, называлась «Topological sorting of large networks» и была написана в прямой связи с методом критического пути (CPM) и сетевым планированием крупных инженерных проектов той эпохи — задача возникла не в теоретической информатике, а в практике управления сложными проектами.

📌 DFS-подход к топологической сортировке появился как побочный продукт куда более общей работы Роберта Тарьяна над алгоритмами на графах в середине 1970-х — тот же принцип «порядка выхода из рекурсии» лежит и в основе его же знаменитого алгоритма поиска компонент сильной связности, опубликованного всего парой лет раньше.

📌 Центральный класс в библиотеке Apache Airflow, вокруг которого строится вся система, в коде называется именно DAG — настолько буквально, что пользователи библиотеки в обиходе называют свои пайплайны данных просто «дагами», даже не всегда задумываясь, что это прямая отсылка к теории графов и требованию ацикличности.

📌 Классическая утилита make, ставшая прообразом современных систем сборки (от CMake до Bazel), решала задачу определения порядка компиляции файлов через обход графа зависимостей ещё в 1976 году — за десятилетия до того, как «топологическая сортировка» стала стандартной темой университетских курсов по алгоритмам.

Лайфхаки

💡 Быстрая проверка «а нужен ли мне вообще DAG» — задай себе вопрос: может ли какое-то подмножество моих задач образовать взаимную зависимость по кругу? Если ответ «да» — сначала нужно чинить саму спецификацию зависимостей, никакой алгоритм топологической сортировки эту проблему не решит, он лишь честно скажет, что решения не существует.

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

💡 Для очень глубоких или длинных цепочечных графов предпочитай алгоритм Кана или итеративный DFS с явным стеком вместо рекурсивного DFS — это тот же урок про ограничение глубины рекурсии Python, что и в уроках про деревья, только применённый к графам.

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

💡 При отладке пайплайна на основе DAG (Airflow, Dagster, самописный граф задач) в первую очередь выведи на экран входящие степени всех вершин — задача, чья степень никогда не доходит до нуля, точно указывает, где именно в графе зависимостей закралась ошибка.

💡 Простой способ проверить корректность уже построенного топологического порядка (например, в собственной реализации при отладке) — пройтись по всем рёбрам графа и убедиться, что позиция начала каждого ребра в списке меньше позиции его конца; это проверка за $O(E)$, которая мгновенно ловит ошибки в реализации алгоритма.

Топологическая сортировка — редкий пример алгоритма, который одновременно предельно прост в объяснении (упорядочить дела с учётом зависимостей) и лежит в фундаменте практически всей современной инфраструктуры вычислений: от команды make, скомпилировавшей самый первый Unix, до вызова loss.backward(), который ты, возможно, написал сегодня утром. Каждый раз, когда фреймворк глубокого обучения корректно вычисляет градиенты сколь угодно сложной, ветвящейся архитектуры, под капотом работает ровно тот же принцип, который ты только что разобрал на графах курсов и установочных пакетов. Дальше в курсе граф снова станет ареной действия — уже со взвешенными рёбрами и вопросом не «в каком порядке», а «каким кратчайшим путём», и первым таким алгоритмом станет алгоритм Дейкстры.