Доказательство существования и два алгоритма + обсуждение

1) Доказательство: любой конечный DAG имеет топологическую сортировку

Пусть G = (V, E) — конечный ориентированный ациклический граф. Покажем, что в G есть вершина с входной степенью 0 (исток). Предположим противное: каждая вершина имеет входную степень ≥ 1. Тогда для любой вершины v существует предок u1 → v; для u1 существует предок u2 → u1 и т.д. Построим бесконечную последовательность предков v, u1, u2, ... . Но V конечен, поэтому по принципу Дирихле появится повторение вершины, т.е. образуется цикл — противоречие с ацикличностью. Значит в G есть вершина s с indegree(s) = 0.

Удалим s и все исходящие из неё рёбра, получим меньший конечный DAG. По индукции снова найдём вершину с нулевой входной степенью и т.д. Таким образом можно по шагам удалить все вершины; порядок удаления даёт топологическую сортировку (ребро u→v всегда удаляется раньше, чем v, следовательно u будет стоять раньше v в порядке). Это конструктивное доказательство и лежит в основе алгоритма Кана.

Альтернативное доказательство: с помощью DFS — возьмём обратный порядок завершения (reverse postorder) при обходе в глубину; из-за отсутствия обратных рёбер для DAG этот порядок будет топологической сортировкой.

2) Алгоритм Кана (псевдокод)

Вход: ориентированный граф G = (V, E)
Выход: список topo (топологический порядок) или сообщение о цикле

Инициализация:

indeg[v] = входная степень v для всех v ∈ VQ = очередь (или приоритетная очередь, если нужен детерминированный порядок)для всех v: если indeg[v] == 0, положить v в Qtopo = пустой список

Основной цикл:
while Q не пусто:
v = Q.pop() // pop из очереди
append v в topo
for каждое ребро v -> w:
indeg[w] -= 1
if indeg[w] == 0:
Q.push(w)

После цикла:
if |topo| < |V|:
обнаружен цикл (нет топологической сортировки)
else:
вернуть topo

Комментарии:

Если Q — FIFO, порядок зависит от порядка добавления; если Q — priority queue (по имени вершины), получим лексикографически наименьшую топологию.Алгоритм детектирует цикл, так как в цикле у всех вершин indeg ≥ 1 и они никогда не попадут в Q.

3) DFS-алгоритм (построение по обратному времени выхода)

Вход: G = (V, E)
Выход: список topo или сообщение о цикле

Инициализация:

state[v] ∈ {white, gray, black}, все whitetopo_list = пустой стек/список

Функция DFS_visit(v):
state[v] = gray
for каждое ребро v -> w:
if state[w] == white:
DFS_visit(w)
else if state[w] == gray:
обнаружен цикл -> остановить и вернуть ошибку
state[v] = black
push v в topo_list // сохранить по выходу из вершины

Главный цикл:
for v в V:
if state[v] == white:
DFS_visit(v)

Если цикла не обнаружено, вернуть reverse(topo_list) (или выталкивать в начало списка при выходе — тогда не надо переворачивать).

Комментарии:

Обнаружение back-edge (v->w, где w.gray) означает цикл.Можно реализовать без рекурсии (с явным стеком).

4) Сложность и поведение на разреженных/плотных графах

Временная сложность (при представлении списками смежности):

Оба алгоритма работают за O(|V| + |E|).
Kahn: инициализация indeg — O(|V| + |E|) для подсчёта; основной цикл обновляет каждое ребро ровно один раз.DFS: каждое ребро рассматривается один раз при обходе, каждая вершина посещается один раз.

Память:

Хранение графа: O(|V| + |E|) для списков смежности; O(|V|^2) для матрицы смежности.Доп. массив indeg (Kahn) — O(|V|); state/стек для DFS — O(|V|).

Влияние плотности (E относительно V):

При списках смежности оба алгоритма масштабируют одинаково: при разреженных графах (E ≈ O(V)) — почти линейно; при плотных графах (E ≈ Θ(V^2)) — O(V^2).При матрице смежности DFS и Kahn, если реализовать проверку соседей путём сканирования строки матрицы, оба станут O(V^2) даже при малом E, что плохо для разреженных графов.Константы и поведение:
Kahn: имеет небольшую константу работы на вершину + уменьшение indeg для каждого ребра; очень удобен для итеративных/параллельных/инкрементальных реализаций и для получения "уровней" (можно взять все вершины с indeg=0 одновременно — параллельный шаг).DFS: простая рекурсивная реализация, полезна если уже используется DFS; может давать меньшее число инвалидаций памяти (нет массива indeg), но требует стек глубины O(V) (рекурсивный или явный). Для очень больших глубин возможен переп/переполнение стека при рекурсивной реализации.Детектирование цикла: оба детектируют; DFS обнаруживает сразу при встрече back-edge; Kahn — когда очередь опустеет и вершины остались.

Выбор на практике:

Если нужен любой топологический порядок — оба подходят.Если нужен детерминированный конкретный порядок (например, лексикографический) — Kahn + priority queue даст контроль над выбором.Для параллельного выполнения/уровневой обработки — Kahn удобнее: на каждом шаге можно обработать одновременно все current-zero-indegree вершины.DFS обычно короче в коде и даёт reverse-postorder, который часто полезен (компиляторы используют reverse-postorder для обхода графов потока управления).

5) Применения

Системы сборки (make, Bazel, ninja и т.п.)

Модель: таргеты/файлы — вершины, зависимость «target A зависит от B» — ребро B → A (B должен быть построен перед A).Топологическая сортировка даёт корректный порядок сборки: каждый таргет собирается после всех своих зависимостей.Параллелизм: на каждом шаге можно запустить сборку всех таргетов с indeg=0 (независимые таргеты) — реализует параллельную сборку.Инкрементальные сборки: система пересчитывает локально изменившиеся части DAG, используя топологию для минимальных пересборок.

Планирование задач (таск-менеджеры, CI/CD, планы работ)

Модель: задачи с предшествованием; ребро u→v означает u должен завершиться до старта v.Топологическая сортировка даёт допустимый последовательный порядок выполнения задач.Расширение: вычисление ранних/поздних сроков (earliest start, latest finish) и критического пути — достаточно пройти по топологии и агрегировать длительности.Для многопроцессорного планирования используем уровневую обработку (Kahn): на каждом временном шаге выполняются все свободные задачи с учётом ресурсов.

Оптимизация вычислений в реляционных выражениях / исполнение запросов

Представление: план запроса (операторы: сканирование, фильтра, проекция, join, агрегация и т.д.) могут формировать ориентированный ациклический граф данных/операторов (DAG) — потоки данных от источников к потребителям.Топологическая сортировка определяет корректный порядок оценки операторов: любой оператор может быть выполнен только после того, как выполнены все его входные операторы.В SQL-оптимизаторах и исполнителях:Для плана в виде дерева/DAG обратный порядок завершения (DFS) часто используется для построения физического плана.Для потоковой обработки (dataflow) Kahn-подобный подход позволяет выделять уровни для параллелизма и pipelining.Оптимизации (перестановка операторов) не сводятся к простой топологической сортировке — требуется учёт семантики (коммутативность/ассоциативность join/selection) и стоимости; топологический порядок лишь гарантирует корректность зависимости при выполнении.В вычислениях с материализацией/повторным использованием промежуточных результатов DAG помогает выявить общие подвыражения (common subexpressions) и порядок их вычисления/кеширования.

6) Краткие рекомендации по выбору

Представление списка смежности + оба алгоритма: O(V+E); обычно это лучший выбор.Если нужен параллелизм по уровням или явная control над порядком — предпочесть Kahn.Если нужна простота реализации и доступен stack/рекурсия — DFS хорош.Для огромных графов, где глубина может быть большой и рекурсия опасна — использовать итеративный DFS или Kahn.

Если хотите, могу:

показать пример шаг за шагом для конкретного DAG,привести реализацию с приоритетной очередью (лексикографическая сортировка),обсудить, как топологический порядок используется внутри конкретной системы сборки (например, make vs Bazel).