Информатика / Алгоритмы и анализ данных

Топологическая сортировка Кана по входящим степеням

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

Опубликовано: 21 октября 2026 г.Обновлено: 21 октября 2026 г.

Формула

d_{in}(v)\leftarrow d_{in}(v)-1\quad\text{при удалении дуги }u\to v;\qquad |L|=|V|\iff G\text{ ацикличен}

Схема Зависимости: нулевые степени A и B

Один допустимый порядок: A, B, C, D, E

Обозначения

$G$: конечный ориентированный граф зависимостей, не применяется
$d_{in}(v)$: текущая входящая степень в ещё не удалённой части графа, число дуг
$L$: последовательность уже выведенных вершин, не применяется
$V$: множество всех вершин исходного графа, не применяется

Условия применения

Дуга u→v означает, что u должно предшествовать v. Начальные входящие степени учитывают все дуги, после чего алгоритм изменяет их при логическом удалении вершин. Любой DAG имеет вершину с нулевой входящей степенью; если граф содержит цикл, полный топологический порядок невозможен.

Ограничения

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

Подробное объяснение

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

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

Почему остановка раньше времени обнаруживает цикл? В оставшейся конечной части каждая вершина имеет входящую дугу из этой же части. Если двигаться против дуг к предшественникам, какая-то вершина повторится. Повтор задаёт ориентированный цикл. Обратно, вершины цикла не могут первыми получить нулевую степень, пока сам цикл не разорван.

Для списков смежности начальные степени считают за O(|V|+|E|), затем каждую вершину и дугу обрабатывают один раз. С обычной очередью итог также линейный. Если нужно выбирать минимальное имя из всех готовых, вместо очереди используют кучу; добавляется стоимость операций с приоритетом.

Топологический порядок — последовательность допустимого выполнения, а не обязательно единственное или оптимальное расписание. Чтобы найти ранние сроки, нужно дополнительно учитывать длительности и максимум по предшественникам. Нельзя интерпретировать номер в L как время окончания работы.

Как пользоваться формулой

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

Историческая справка

Алгоритм связан со статьёй Артура Кана «Topological sorting of large networks», опубликованной в Communications of the ACM в ноябре 1962 года. Историческая задача состоит в линейном упорядочении сети зависимостей, а не в сортировке чисел по величине. Именно направление дуг отличает топологический порядок от обычного сравнения ключей. В современном преподавании рядом рассматривают другой подход — обратный порядок завершения DFS для ациклического графа; например, так организована тема в курсе MIT 6.006. Два способа дают один тип допустимого результата, но поддерживают разные служебные данные. В варианте Кана главным инвариантом остаётся число ещё не удалённых входящих дуг, что делает алгоритм наглядным для практических зависимостей.

Историческая линия формулы

Названный вариант использует удаление вершин с нулевой входящей степенью и связывается с публикацией А. Б. Кана 1962 года. Топологическую сортировку можно выполнить и через DFS; эти алгоритмы не следует смешивать по названию, даже если оба работают за линейное время на списках смежности.

Пример

Пусть зависимости заданы дугами A→C, B→C, C→D, B→E. Начальные степени A = 0, B = 0, C = 2, D = 1, E = 1. Если среди готовых выбирать алфавитно, сначала выводим A: степень C становится 1. После B степени C и E становятся нулевыми. Выбираем C, после него готова D; среди D и E выбираем D, затем E. Ответ L = A, B, C, D, E. Все пять вершин выведены, значит граф ацикличен. Если добавить дугу D→B, после A очередь опустеет: B, C, D связаны циклом B→C→D→B, а E тоже остаётся заблокированной зависимостью от B. Недостаточно просто отсортировать начальные степени: они меняются после каждого удаления.

Частая ошибка

Не переворачивайте дуги зависимостей. Не сортируйте один раз по начальной степени: это не заменяет обновления. Не объявляйте единственным один из нескольких допустимых порядков. Не публикуйте частичный список как успешный результат для всего графа. Не приравнивайте все оставшиеся вершины к вершинам цикла: часть может лишь зависеть от него.

Практика

Задачи с решением

Два правильных порядка

Условие. Граф содержит только A→C и B→C. Перечислите все топологические порядки.

Решение. A и B независимы, но обе должны стоять перед C. Возможны A,B,C и B,A,C; других перестановок нет.

Ответ. Два порядка: ABC и BAC.

Заблокированный хвост

Условие. Дуги A→B, B→A, B→C. Есть ли вершина с начальной входящей степенью ноль?

Решение. Степени A = 1, B = 1, C = 1. Очередь пуста сразу. Цикл образуют A и B; C не лежит на цикле, но зависит от B.

Ответ. Нет; полный порядок невозможен.

Дополнительные источники

https://doi.org/10.1145/368996.369025
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-14-depth-first-search-dfs-topological-sort/
https://algs4.cs.princeton.edu/42digraph/Topological.java.html

Связанные формулы

Информатика

Поиск в глубину: дерево обхода и времена входа и выхода

$u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v$

Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.

Информатика

Сильные компоненты: два обхода алгоритма Косарайю

$u\sim v\iff(u\leadsto v)\land(v\leadsto u),\qquad T=O(|V|+|E|)$

Сильная компонента ориентированного графа объединяет вершины, достижимые друг из друга в обоих направлениях. Алгоритм Косарайю находит такие группы двумя обходами в глубину с разворотом всех дуг.

Информатика

Мосты графа: критерий через времена входа и low

$(v,u)\text{ — мост}\iff low(u)>t_{in}(v),\quad u\text{ — ребёнок }v\text{ в DFS}$

Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. DFS обнаруживает его, если поддерево ребёнка не имеет обходного ребра к родителю или его предкам.

Информатика

Точки сочленения: критерий low и отдельное правило корня

$v\ne root:\quad v\text{ — точка сочленения}\iff\exists u\text{ — ребёнок}:low(u)\ge t_{in}(v)$

Точка сочленения — вершина, удаление которой вместе с инцидентными рёбрами увеличивает число компонент связности. Для некорневой вершины DFS использует нестрогое сравнение low ребёнка с временем входа.