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

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

¶История

Понятие топологической сортировки возникло в середине XX века в связи с развитием теории графов и алгоритмов. Одним из первых алгоритмов, решающих эту задачу, стал алгоритм Кана, опубликованный в 1962 году Артуром Б. Каном (Arthur B. Kahn) в статье «Topological sorting of large networks». Независимо от него, в 1964 году Роберт Тарьян (Robert Tarjan) предложил алгоритм на основе поиска в глубину (DFS), который также позволяет выполнить топологическую сортировку. Оба алгоритма остаются классическими и широко используются в компьютерных науках.

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

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

¶Алгоритмы

¶Алгоритм Кана (Kahn’s algorithm)

Алгоритм Кана основан на последовательном удалении вершин с нулевой входящей степенью (количество входящих рёбер). Шаги:

1. Вычислить входящую степень для каждой вершины.
2. Поместить в очередь все вершины с нулевой входящей степенью.
3. Пока очередь не пуста:

• Извлечь вершину u из очереди и добавить её в результат.
• Для каждого исходящего ребра (u → v) уменьшить входящую степень v на 1.
• Если входящая степень v стала нулевой, добавить v в очередь.

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

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

¶Алгоритм на основе поиска в глубину (DFS-based algorithm)

Алгоритм Тарьяна использует обход графа в глубину:

1. Для каждой непосещённой вершины запустить рекурсивный DFS.
2. При завершении обработки вершины (после обхода всех её потомков) добавить вершину в стек (или в начало списка).
3. После обработки всех вершин стек содержит вершины в порядке, обратном топологическому, поэтому результат получается извлечением из стека.

Если в процессе DFS встречается обратное ребро (ведущее к вершине, которая уже находится в текущем стеке рекурсии), это свидетельствует о наличии цикла.

Временная сложность: O(V + E). Алгоритм требует дополнительной памяти для стека рекурсии (глубиной до V) и для хранения состояния вершин.

¶Пример

Рассмотрим граф, описывающий последовательность одевания: носки → ботинки, брюки → ботинки, брюки → рубашка, рубашка → пиджак. Топологическая сортировка может дать порядок: носки, брюки, рубашка, ботинки, пиджак. Другой допустимый порядок: брюки, носки, рубашка, пиджак, ботинки. Оба варианта корректны, так как сохраняют все зависимости.

¶Применение

¶Планирование задач и управление проектами

Топологическая сортировка используется в методах сетевого планирования (например, метод критического пути — CPM) для определения порядка выполнения работ, зависящих друг от друга. Каждая вершина графа представляет задачу, а ребро — зависимость: задача u должна быть завершена до начала задачи v.

¶Системы сборки программного обеспечения

В утилитах сборки (например, Make, Gradle, Maven) топологическая сортировка применяется для определения порядка компиляции модулей, когда один модуль зависит от другого. Граф зависимостей строится из описаний проекта, и сортировка гарантирует, что зависимости будут собраны раньше зависимых модулей.

¶Компиляторы и обработка языков

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

¶Обработка баз данных

В системах управления базами данных (СУБД) топологическая сортировка применяется для разрешения зависимостей между таблицами при выполнении запросов с соединениями (JOIN) или при определении порядка миграций схемы.

¶Анализ зависимостей в пакетных менеджерах

Менеджеры пакетов (например, npm, pip, apt) используют топологическую сортировку для установки пакетов в порядке, при котором зависимости устанавливаются раньше, чем пакеты, которые их используют.

¶Свойства и ограничения

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

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

• Топологическая сортировка является частным случаем задачи линейного расширения частичного порядка.
• В русскоязычной литературе термин «топологическая сортировка» часто сокращается до «топсорт».
• Алгоритм Кана иногда называют «алгоритмом удаления вершин» или «алгоритмом с нулевой степенью».
• В 2010-х годах топологическая сортировка стала применяться в задачах машинного обучения, в частности, при построении графов знаний и обучении нейронных сетей на графовых структурах.

¶Источники

• Kahn, A. B. (1962). «Topological sorting of large networks». Communications of the ACM, 5(11), 558–562.
• Tarjan, R. E. (1972). «Depth-first search and linear graph algorithms». SIAM Journal on Computing, 1(2), 146–160.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). «Алгоритмы: построение и анализ» (3-е изд.). — М.: Вильямс.
• Седжвик, Р. (2016). «Фундаментальные алгоритмы на C++». — М.: Вильямс.