Алгоритмы с нуля
Топологическая сортировка: упорядочивание DAG через Kahn и DFS
Ты знаешь как обходить граф: DFS ныряет глубоко, BFS распространяется широко, а связные компоненты считают отдельные части. Теперь вопрос острее. Предположим граф это список задач, где стрелка A → B значит “A должно случиться до B”: предварительные требования курсов, шаги сборки, установки пакетов, зависимости формул в таблице. В каком порядке ты можешь сделать все задачи так, чтобы ничего никогда не начиналось до того как закончено то, от чего оно зависит? Такой порядок называется топологический порядок. Он не единственный — часто существует много валидных порядков — но он вообще существует только если граф зависимостей не имеет цикла. Если задача A нужна B, а B нужна A, никакой порядок не может удовлетворить обе. Этот урок учит два алгоритма чтобы получить топологический порядок и, как бесплатный бонус, обнаруживать когда никакого порядка нет потому что граф содержит цикл.
После этого урока ты можешь дать определение топологическому порядку: линейное перечисление вершин ориентированного ациклического графа (DAG) такое, что для каждого ребра u → v вершина u появляется до v. Ты понимаешь почему такой порядок существует тогда и только тогда когда граф ацикличен. Ты можешь написать алгоритм Kahn: вычисли полустепень захода каждой вершины, добавь в очередь все вершины с полустепенью захода 0, многократно извлекай одну в вывод и уменьшай полустепень захода её соседей, добавляя в очередь любую достигшую 0. Ты знаешь тест на цикл: если вывод содержит меньше чем V вершин, граф имеет цикл и топологического порядка нет. Ты также можешь написать вариант с DFS: запусти DFS и помести каждую вершину в стек когда она завершается (post-order), потом разверни стек. Ты знаешь что оба работают за O(V + E) времени и O(V) памяти. Следующие уроки строятся на упорядоченных DAG для кратчайших путей и планирования.
Что это топологический порядок?
Топологический порядок (или топологическая сортировка) ориентированного графа это линейное расположение всех его вершин такое, что для каждого ориентированного ребра u → v вершина u идёт до вершины v в списке. Читай ребро u → v как “u должно идти первым”. Валидный топологический порядок соблюдает каждое такое ограничение сразу.
Он существует только для DAG
Топологический порядок существует тогда и только тогда когда граф это ориентированный ациклический граф (DAG) — ориентированный граф без цикла. Причина проста. Если бы был цикл a → b → c → a, то a должно идти до b, b до c, и c до a. Это требует чтобы a шло до самого себя, что невозможно. Так цикл блокирует любой валидный порядок. Наоборот, каждый DAG имеет хотя бы один валидный порядок (часто много). Топологический порядок обычно не единственный: две задачи без зависимости между собой могут идти в любом относительном порядке.
Реальный пример: предварительные требования курсов
Каждая стрелка значит “предварительное требование для”. Ты должен закончить исходный курс до прохождения целевого.
intro
/ \
v v
data-structures discrete-math
| \ /
| v v
v algorithms
databases |
v
mlРёбра (список смежности):
intro: [data-structures, discrete-math]
data-structures: [algorithms, databases]
discrete-math: [algorithms]
algorithms: [ml]
databases: []
ml: []Валидный план должен взять intro первым (ничто не зависит от того что что-то сделано до него) и ml последним (он зависит от algorithms, который зависит от двух более ранних курсов). Существует несколько валидных порядков; алгоритм ниже производит один конкретный.
Алгоритм Kahn: снимай то, у чего не осталось предварительных требований
Идея алгоритма Kahn интуитивна. Полустепень захода вершины это сколько рёбер указывает в неё — сколько у неё невыполненных предварительных требований. Вершина с полустепенью захода 0 не имеет ничего блокирующего её, так она может идти следующей. Возьми одну, выведи её, и “удали” её из графа уменьшив полустепень захода каждой вершины, на которую она указывала. Некоторые из них могут теперь упасть до 0 и стать доступными. Повторяй пока каждая вершина не размещена.
- Вычисли полустепень захода каждой вершины.
- Помести все вершины с полустепенью захода 0 в очередь.
- Пока очередь не пуста:
- Извлеки вершину v, добавь её в порядок вывода.
- Для каждого соседа w вершины v: уменьши
inDegree[w]. Если она становится 0, добавь w в очередь.
- Если вывод содержит все V вершин, это топологический порядок. Если в нём меньше чем V, оставшиеся вершины застряли в цикле — порядка нет.
Разобранная трассировка Kahn на графе курсов
Полустепени захода для начала (считаем входящие рёбра):
intro: 0 data-structures: 1 discrete-math: 1
algorithms: 2 databases: 1 ml: 1Initial: only intro has in-degree 0.
queue = [intro], order = []
Pop intro. order = [intro].
decrement data-structures -> 0 (enqueue), discrete-math -> 0 (enqueue).
queue = [data-structures, discrete-math]
Pop data-structures. order = [intro, data-structures].
decrement algorithms 2->1 (not 0), databases 1->0 (enqueue).
queue = [discrete-math, databases]
Pop discrete-math. order = [intro, data-structures, discrete-math].
decrement algorithms 1->0 (enqueue).
queue = [databases, algorithms]
Pop databases. order = [..., databases]. No neighbors.
queue = [algorithms]
Pop algorithms. order = [..., algorithms].
decrement ml 1->0 (enqueue).
queue = [ml]
Pop ml. order = [..., ml]. No neighbors.
queue = []
Output has all 6 vertices -> valid topological order:
intro -> data-structures -> discrete-math -> databases -> algorithms -> mlКаждая стрелка в графе указывает вперёд в этом списке, так порядок валиден.
Вариант с DFS: разверни порядок завершения
Второй алгоритм использует поиск в глубину. Запусти DFS по всему графу. Когда вершина завершается — после того как все её исходящие рёбра полностью исследованы — помести её в стек. Это post-order (постфиксный порядок). После завершения DFS, разверни стек (или извлекай из него) чтобы получить топологический порядок.
Почему это работает: вершина завершается только после того как всё достижимое из неё уже завершилось. Так в post-order вершина появляется до всех своих потомков. Разворот переворачивает это в “до всего от чего она зависит” — ровно топологическое ограничение. Для графа курсов один запуск DFS производит post-order ml, algorithms, databases, data-structures, discrete-math, intro; в развёрнутом виде это intro -> discrete-math -> data-structures -> databases -> algorithms -> ml, другой валидный порядок (отличный от Kahn, но столь же корректный).
Два способа обнаружить цикл
Оба алгоритма заодно работают детекторами циклов:
- Kahn: если финальный вывод содержит меньше чем V вершин, цикл остаётся. Вершины внутри цикла никогда не достигают полустепени захода 0, так их никогда не добавляют в очередь.
- DFS: отслеживай вершины сейчас в стеке рекурсии (множество “в процессе”). Если DFS достигает вершину уже в процессе, это обратное ребро замыкает цикл — топологического порядка нет.
Алгоритм Kahn с полустепенями захода и очередью
1
function topoSortKahn(adj) {
2
// 1. Compute in-degree of every vertex
3
const inDegree = {};
4
for (const v of Object.keys(adj)) inDegree[v] = 0;
5
for (const v of Object.keys(adj)) {
6
for (const w of adj[v]) inDegree[w]++;
7
}
8
9
// 2. Enqueue every vertex with no prerequisites
10
const queue = [];
11
for (const v of Object.keys(adj)) {
12
if (inDegree[v] === 0) queue.push(v);
13
}
14
15
// 3. Repeatedly take a free vertex and relax its edges
16
const order = [];
17
while (queue.length > 0) {
18
const v = queue.shift();
19
order.push(v);
20
for (const w of adj[v]) {
21
inDegree[w]--;
22
if (inDegree[w] === 0) queue.push(w);
23
}
24
}
25
26
// 4. Fewer than V placed => a cycle blocked the rest
27
if (order.length < Object.keys(adj).length) {
28
return null; // no topological order exists
29
}
30
return order;
31
}
- L3 Инициализируй полустепень захода каждой вершины как 0.
- L5 Просмотри все рёбра; каждое ребро u -> w добавляет 1 к полустепени захода w.
- L11 Вершина с полустепенью захода 0 не имеет невыполненного предварительного требования: она может идти первой.
- L18 Извлеки свободную вершину из начала очереди (FIFO).
- L19 Добавь её в порядок вывода.
- L21 Удаляя v: каждый сосед теряет одно предварительное требование.
- L22 Если полустепень захода соседа достигает 0, он теперь свободен; добавь его в очередь.
- L27 Если размещена не каждая вершина, остатки образуют цикл: верни null.
Ключевой момент: полустепень захода 0 значит “готова”
Вершина готова к выводу только когда каждое ребро указывающее в неё уже удалено — то есть когда её полустепень захода падает до 0. Очередь Kahn держит ровно множество “сейчас готовых” вершин. Вершина внутри цикла никогда не может достичь полустепени захода 0 (одно из её предварительных требований это она сама, косвенно), так она никогда не входит в очередь. Это ровно почему счёт остатка ниже V сигнализирует цикл.
Запуск алгоритма Kahn на графе курсов
Вариант с DFS: помести при выходе, потом разверни
1
function topoSortDFS(adj) {
2
const visited = new Set();
3
const stack = [];
4
5
function dfs(v) {
6
visited.add(v);
7
for (const w of adj[v]) {
8
if (!visited.has(w)) dfs(w);
9
}
10
stack.push(v); // push on EXIT: post-order
11
}
12
13
for (const v of Object.keys(adj)) {
14
if (!visited.has(v)) dfs(v);
15
}
16
17
return stack.reverse(); // reverse post-order = topological order
18
}
- L6 Отметь v посещённой до исследования её исходящих рёбер.
- L8 Рекурсивно зайди в каждого непосещённого соседа (всё от чего v зависит сначала).
- L10 Помести v только после того как все её потомки завершились: это post-order.
- L13 Пройди по всем вершинам чтобы покрыть и разъединённые части тоже.
- L16 Разверни порядок завершения: вершина теперь предшествует всему на что она указывает.
1
inDegree = { intro:0, data-structures:1, discrete-math:1,
2
algorithms:2, databases:1, ml:1 };
3
queue = [intro];
4
order = [];
Сложность по времени: O(V + E)
Алгоритм Kahn делает постоянный объём работы на вершину и на ребро. Вычисление полустепеней захода просматривает каждое ребро раз: O(E). Поиск начальных вершин с полустепенью захода 0 просматривает каждую вершину раз: O(V). В главном цикле каждая вершина добавляется в очередь и извлекается ровно раз (O(V) всего), и каждое ребро рассматривается ровно раз когда его исходная вершина извлекается и его соседи уменьшаются (O(E) всего). Суммарно: O(V + E).
Вариант с DFS такой же: DFS посещает каждую вершину раз и каждое ребро раз, плюс одно помещение на вершину — O(V + E).
Пример: граф зависимостей с 6 вершинами и 6 рёбрами (граф курсов) работает за O(6 + 6) = O(12) работы, независимо от того как ветвятся зависимости.
Сложность по памяти: O(V)
Отображение полустепеней захода хранит одну запись на вершину: O(V). Очередь может удерживать до V вершин когда многие становятся готовыми сразу: O(V). Список порядка вывода удерживает до V вершин: O(V). Для варианта с DFS множество посещённых и стек рекурсии каждый O(V). Итого: O(V).
(Сам список смежности это O(V + E) входных данных, не считается как дополнительная рабочая память.)
Почему меньше-чем-V значит цикл
Cyclic graph: a -> b -> c -> a (plus an extra a -> d, d in-degree 1)
In-degrees: a:1, b:1, c:1, d:1 -> NO vertex has in-degree 0.
queue starts empty.
The while loop never runs.
order = [] (0 vertices placed)
0 < 4 -> return null: no topological order.
Every vertex in the cycle keeps an unmet prerequisite forever,
so none ever reaches in-degree 0. They are exactly the leftovers.Полезная диагностика: вершины отсутствующие в выводе это ровно те что застряли в (или ниже по потоку от) цикле.
В топологическом порядке ребро u -> v значит:
Топологический порядок существует для ориентированного графа тогда и только тогда когда граф:
В алгоритме Kahn какие вершины добавляются в очередь первыми?
В топологической сортировке на основе DFS, когда вершина помещается в стек?
После запуска алгоритма Kahn, как ты узнаёшь что граф имел цикл (так топологического порядка нет)?
DAG зависимостей имеет 10 вершин и 14 рёбер. Сложность по времени O(V + E) соответствует какому общему числу операций?
Почему это работает
Почему два алгоритма? Kahn итеративный, использует очередь, и даёт обнаружение циклов бесплатно через счёт остатка — удобно когда ты также хочешь сообщить какие задачи застряли. Вариант с DFS короче и переиспользует DFS который ты уже знаешь; он естественен когда ты уже идёшь по графу по другой причине. Оба O(V + E). Выбери тот что подходит к коду который у тебя уже есть; результирующие порядки могут отличаться но равно валидны.
Частая ошибка
Забывание что он не единственный. Две задачи без пути между ними могут появиться в любом порядке, так один и тот же DAG имеет много валидных топологических порядков. Тесты что проверяют одну точную строку хрупкие. Если тебе нужен детерминированный порядок (для воспроизводимых сборок), используй очередь с приоритетом вместо обычной очереди в Kahn, разрешая ничьи по фиксированному ключу (такому как имя). Версия с обычной очередью здесь детерминирована только потому что порядок ключей входа фиксирован.
Граничные случаи
Цикл значит нет ответа, не неправильный ответ. Топологическая сортировка не определена для графа с циклом — там действительно нет валидного порядка. Не возвращай частичный список и не притворяйся что он отсортирован. Верни ясный сигнал (null, пустой результат, или исключение) чтобы вызывающий знал что граф зависимостей сломан. Проверка счёта остатка (Kahn) или проверка обратного ребра в процессе (DFS) это то что выявляет это.
Ещё практика
Где ты будешь это использовать. Системы сборки упорядочивают единицы компиляции; менеджеры пакетов упорядочивают установки; таблицы пересчитывают ячейки; планировщики задач запускают задания; даже разрешение зависимостей импорта это топологическая сортировка. Всякий раз когда у тебя есть ограничения “X должно случиться до Y” над конечным множеством, моделируй их как DAG и топологически сортируй. Если сортировка не удаётся, ты только что обнаружил циклическую зависимость.
Объясни что такое топологический порядок, когда он существует, как алгоритм Kahn и вариант с DFS производят его, как каждый обнаруживает цикл, и сложность.
Топологический порядок ориентированного ациклического графа (DAG) перечисляет каждую вершину до всех вершин на которые она указывает: для каждого ребра u → v вершина u предшествует v. Он существует тогда и только тогда когда граф не имеет цикла, и обычно не единственный.
Алгоритм Kahn: вычисли полустепень захода каждой вершины, добавь в очередь вершины с полустепенью захода 0, потом многократно извлекай одну в порядок и уменьшай её соседей, добавляя в очередь любую достигшую 0. Если выходит меньше чем V вершин, цикл заблокировал остаток.
Вариант с DFS: запусти DFS, помести каждую вершину при выходе (post-order), потом разверни стек. Обратное ребро к вершине в процессе помечает цикл.
Время: O(V + E). Память: O(V). Оба алгоритма заодно работают детекторами циклов.
Топологическая сортировка это движок за системами сборки, менеджерами пакетов, планировщиками, и разрешением зависимостей. Дальше: упорядоченные DAG питают алгоритмы кратчайших путей и планирования.