Топологическая сортировка — это способ упорядочить вершины ориентированного ациклического графа (DAG) так, чтобы для каждого ребра u → v вершина u шла раньше v.
Проще говоря: если одна задача зависит от другой, то в порядке выполнения зависимость должна стоять раньше. Именно поэтому топосорт часто встречается в IT: от сборки проектов до планировщиков задач и анализа зависимостей.
Где применяется
- определение порядка сборки модулей в проекте
- запуск задач в пайплайнах CI/CD
- разрешение зависимостей пакетов
- составление учебного плана по prerequisite-курсам
- вычисления в графах зависимостей данных
Когда топологическая сортировка возможна
Только если граф без циклов. Если есть цикл, например A → B → C → A, корректный порядок построить нельзя: каждая вершина зависит от другой по кругу.
Два классических алгоритма
1. Алгоритм Кана 🔹
Идея:
- считаем входящую степень (
in-degree) каждой вершины - кладём в очередь все вершины с
in-degree = 0 - извлекаем вершину, добавляем в ответ, уменьшаем степени её соседей
- если у соседа степень стала 0, тоже добавляем в очередь
Если в итоге обработали не все вершины — в графе есть цикл.
Сложность: O(V + E)
Это оптимально для большинства задач.
2. DFS-подход 🔍
Идея:
- запускаем обход в глубину
- после обработки всех потомков добавляем вершину в стек/ответ
- в конце разворачиваем результат
Для поиска цикла удобно использовать 3 цвета:
0— не посещена1— в процессе обхода2— обработана
Переход в вершину цвета 1 означает цикл.
Как понять, что перед вами задача на DAG
Частые формулировки:
- “найти порядок выполнения”
- “есть зависимости между задачами”
- “определить, можно ли пройти все курсы”
- “посчитать количество путей в ациклическом графе”
- “найти самый длинный путь в DAG”
Типовые задачи на DAG 🚀
- Проверка существования порядка: есть ли цикл
- Восстановление порядка: вывести любой корректный топосорт
- Уникальность порядка: если на каждом шаге доступна только одна вершина с нулевой входящей степенью
- Подсчёт путей: делается через DP по топологическому порядку
- Longest Path in DAG: тоже через DP, в отличие от общего графа решается эффективно
Практический совет для собеседований 💡
Если видите зависимости и отсутствие циклов — почти наверняка нужен DAG. Если нужно “упорядочить”, “проверить возможность выполнения” или “распространить значения по зависимостям” — начинайте с топологической сортировки.
Главная мысль
Топосорт — это не просто алгоритм “из учебника”, а базовый инструмент для реальных систем, где важен порядок выполнения. Понимание DAG помогает решать задачи чище, быстрее и с правильной асимптотикой. 📚
Посмотрите подборку каналов про IT — там много полезного по алгоритмам, разработке и системному мышлению.