Алгоритм топологической сортировки графа

Топологическая сортировка – это упорядочение вершин ориентированного ациклического графа (ОАГ, DAG) такое, что каждая дуга направлена от вершины с меньшим номером в порядке к вершине с большим. По существу, это линейное продолжение частичного порядка, заданного отношением достижимости по дугам. В учебных и прикладных задачах топологический порядок используется для планирования работ с зависимостями, компиляции модулей, упорядочения вычислений по формулам, разрешения зависимостей в сборке проектов.

Для ЕГЭ по информатике владение темой даёт:

1. уверенное оперирование моделями графов и частичных порядков;

2. умение строить корректные алгоритмы на графах и оценивать их сложность;

3. навыки доказательства корректности через инварианты;

4. готовность к задачам на поиск циклов, работу со списками смежности, очередями/стеками и обходами.

Формальная постановка и критерий применимости

Необходимое и достаточное условие существования Топологический порядок существует тогда и только тогда, когда G ацикличен.

• Если есть цикл, ни одна вершина цикла не может оказаться «раньше» всех остальных из цикла.

• Если граф ацикличен, порядок существует (док-во конструктивно алгоритмами ниже).

Две канонические стратегии

1. Алгоритм Кана (по не входящим дугам)
   

   Идея. На каждом шаге брать любую вершину с нулевой полустепенью захода (in-degree = 0), добавлять её в результат и «удалять» вместе с исходящими дугами, уменьшая in-degree у её соседей.

   Структуры данных.

   • Списки смежности;

   • Массив in[v] – полустепени захода;

   • Очередь/дек (или приоритетная очередь для детерминированного выбора).

   Инвариант корректности. Множество вершин с in-degree = 0 – это текущие минимальные элементы частичного порядка; ни одна дуга не идёт внутрь этого множества.

   Псевдокод (концептуально).

   1. Вычислить in[v] для всех v.

   2. Поместить все v с in[v]=0 в структуру S.

   3. Пока S не пуста:
      а) извлечь v из S, дописать v в ответ;
      б) для каждого u из Adj[v] уменьшить in[u]; если in[u]=0, добавить u в S.

   4. Если длина ответа < n – цикл (провалена ацикличность).

   Сложность. O(V+E) по времени, O(V) по памяти (плюс хранение графа).

   Практическое правило 1. Для «лексикографически минимального» топологического порядка используйте минимальную кучу/приоритетную очередь, извлекая каждый раз вершину с наименьшим номером – типичный формат детерминированного ответа в задачах.

2. DFS-метод (по временам выхода)
   

   Идея. Выполнить DFS; вершины записывать в стек (или в начало списка) в момент завершения обработки вершины (время выхода). Обратный порядок этих «времен выхода» – топологический.

   Инвариант корректности. Для дуги (u,v) завершение v происходит не позже завершения u (иначе была бы обратная дуга в стек рекурсии), значит в обратном порядке u предшествует v.

   Обнаружение циклов. При посещении окрашиваем вершины в белый/серый/чёрный; встреча ребра в серую вершину означает цикл (обратное ребро).

   Сложность. O(V+E); потребление стека – до O(V).

   Практическое правило 2. DFS-метод удобен, когда одновременно требуется проверка на цикл и топологический порядок. Его же легко адаптировать для расчленения на компоненты сильной связности (Косарайю/Таръян), если задача этого требует.

Свойства, неоднозначность и уникальность

• Множественность ответов. Если на некотором шаге Кана множество S содержит более одной вершины, существует несколько корректных порядков.

• Критерий уникальности. Топологический порядок единственный, если на каждом шаге алгоритма Кана множество S одноэлементно (при фиксированном способе выбора); эквивалентно – частичный порядок является линейным.

• Проверка результата. Для полученной последовательности достаточно проверить все дуги (u, v): индекс u меньше индекса v. Это даёт верификацию за O(V+E) при наличии индексного массива.

Практическое правило 3. В задачах с «дополнительными условиями» (минимизировать/максимизировать лексикографию) управляйте порядком выбора из S; в DFS – управляйте порядком обхода смежности.

Выбор представления графа и инженерные детали

• Списки смежности предпочтительны: линейность по сумме степеней.

• Матрица смежности годится для очень плотных графов, но дорога по памяти O(n²).

• Хранение in-degree. Удобно вычислять одним проходом по всем спискам смежности.

• Стратегии выбора в S.
  

  • Очередь FIFO – произвольный корректный порядок;

  • Мину-куча – лексикографически минимальный;

  • Макс-куча – лексикографически максимальный.

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

Доказательные элементы корректности

1. Алгоритм Кана
   

   • Корректность шага. Вершина с in=0 не имеет предшественников, значит может стоять раньше всех остальных ещё не размещённых.

   • Сохранение инварианта. Удаление вершины и её исходящих дуг не создаёт новых предшественников для оставшихся вершин.

   • Завершение. Если граф ацикличен, на каждом шаге существует хотя бы одна вершина с in=0 (минимальный элемент частичного порядка). Если множество S опустело раньше, чем размещены все вершины, – существует цикл.

2. DFS-метод
   

   • Лемма о времени выхода. Если (u, v) ∈ E, то время выхода tout(v)<tout(u); иначе обнаружится обратное ребро в серую вершину. Следовательно, обратная сортировка по tout.

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

Оба подхода работают за O(V+E) и являются асимптотически оптимальными, так как нужно хотя бы прочитать вход (все вершины и дуги). Память доминируется хранением графа; сверх него требуются:

• массив степеней (Кан), Θ(V);

• массив цветов/времён и стек (DFS), Θ(V).

Практическое правило 5. Для очень больших графов:

• избегайте рекурсивного DFS (переполнение стека) – используйте явный стек;

• выбирайте потоковую обработку: счётчик in-degree можно считать по мере чтения ребёр.

Типичные ошибки и как их предотвратить

1. Не обнуляют счётчики степеней перед заполнением – неверные in-degree.

2. Забывают уменьшать in-degree у всех выходов удаляемой вершины – «застревание» алгоритма.

3. Игнорируют дубликаты рёбер – in-degree считается завышенным.

4. Неверно трактуют цикл – отсутствие полного результата в Кане обязательно означает цикл.

5. Рекурсивный DFS без защиты – падение стека на длинных цепочках.

6. Непредсказуемый порядок – при требовании детерминизма используйте приоритетную структуру.

Как тема соотносится с ЕГЭ по информатике

• Графы и алгоритмы. Часто требуется распознать ацикличность, упорядочить события, найти корректный порядок вычислений формул.

• Асимптотика. Умение без вычислительной «экзотики» получить O(V+E) и объяснить, где тратится время.

• Доказательства. Инварианты и леммы о корректности – важная часть качественных решений.

• Структуры данных. Очереди, стеки, кучи – базовые инструменты, которые регулярно встречаются в заданиях с программированием и анализом псевдокода.

Пять упражнений (академический формат, без кода)

Упражнение 1. Инвариант Кана и цикл.
Дан ориентированный граф с 10 вершинами и неизвестной структурой.
а) Сформулируйте инвариант множества S (вершин с in-degree = 0) на каждом шаге алгоритма Кана.
б) Докажите, что если на некотором шаге S пусто, а ещё не все вершины помещены в порядок, то в графе есть цикл.
в) Сформулируйте достаточное условие уникальности топологического порядка в терминах мощности S.

Упражнение 2. Сложность и представление.
Пусть граф задан списками смежности, V=n, E=m.
а) Оцените время и память алгоритма Кана и DFS-метода.
б) Сравните с матрицей смежности: как меняются оценки?
в) Приведите пример класса графов, где матрица может быть оправдана.

Упражнение 3. Лексикографически минимальный порядок.
Дано условие: требуется лексикографически минимальная топологическая сортировка.
а) Опишите модификацию Кана, гарантирующую такой результат.
б) Докажите, что полученная последовательность действительно минимальна среди всех топологических порядков.
в) Оцените дополнительную сложность по времени и памяти по сравнению с обычной очередью.

Упражнение 4. DFS и обнаружение цикла.
Рассмотрим DFS с раскраской «белый–серый–чёрный».
а) Докажите, что наличие ребра из текущей вершины в «серую» означает цикл.
б) Объясните, почему обратная сортировка по временам выхода корректна только при отсутствии таких рёбер.
в) Предложите итеративный вариант DFS, эквивалентный рекурсивному по порядку посещения.

Упражнение 5. Верификация ответа.
Дан массив ord[1..n] – предполагаемый топологический порядок вершин 1..n.
а) Опишите алгоритм проверки корректности порядка за O(n+m).
б) Докажите его корректность.
в) Укажите, какие ошибки входных данных (дубли рёбер, петли) должны быть явно выявлены при проверке. 

Заключение

Топологическая сортировка – строгое и при этом простое по идее средство линейного упорядочения зависимостей в ориентированных ациклических графах. Две канонические реализации – алгоритм Кана и DFS по временам выхода – дают оптимальную асимптотику O(V+E), естественные инварианты и надёжные критерии наличия цикла. Для подготовки к ЕГЭ этот материал укрепляет базовую графовую культуру: умение выбирать структуру данных, формулировать и проверять инварианты, добиваться детерминированных ответов и грамотно обосновывать корректность и сложность решений.