Топологическая сортировка ориентированных графов: Планирование зависимостей
В разработке программного обеспечения (сборка модулей), строительстве и управлении проектами постоянно возникает задача: в каком порядке выполнять работу, если одни задачи жестко зависят от других? Например, вы не можете начать красить стены, пока не построена крыша. В теории графов эта математическая проблема изящно решается с помощью алгоритма топологической сортировки.
Математической моделью для таких задач с зависимостями служит Ориентированный ациклический граф (DAG — Directed Acyclic Graph). В нем вершины — это задачи, а направленные дуги от А к Б означают, что задача А должна быть обязательно завершена до начала выполнения задачи Б. Ацикличность — строгое математическое требование: если в графе есть направленный цикл (А ждет Б, Б ждет В, а В ждет А), возникает классический тупик (Deadlock), и выполнить такой проект в принципе невозможно.
Топологическая сортировка — это линейное упорядочивание всех вершин графа такое, что для каждого направленного ребра от u к v, вершина u всегда предшествует вершине v в этом упорядочивании. Результатом является готовое линейное расписание задач.
Существует два классических линейных алгоритма для выполнения топологической сортировки, оба работают за время O(V + E):
- Алгоритм Кана (Kahn's algorithm): основан на отслеживании входящих степеней вершин. Сначала мы находим все задачи, у которых нет никаких зависимостей (входящая степень равна нулю), и помещаем их в очередь. Вынимая задачу из очереди, мы "выполняем" её — удаляем из графа вместе со всеми исходящими от нее ребрами. Если при удалении ребра входящая степень какой-то другой вершины стала равна нулю, мы добавляем и её в очередь. Процесс продолжается до опустошения графа.
- На основе поиска в глубину (DFS): мы запускаем классический алгоритм DFS из случайной непосещенной вершины. Самое главное правило: мы добавляем вершину в результирующий список только после того, как полностью исследуем всех ее потомков (в момент выхода из рекурсии). Полученный список затем просто переворачивается задом наперед, образуя корректную топологическую сортировку.
Топологическая сортировка используется в пакетных менеджерах (npm, apt, pip) для разрешения зависимостей при установке библиотек. Также на DAG-графах строится метод PERT (Program Evaluation and Review Technique) и алгоритм поиска критического пути в управлении проектами: находя самый длинный путь в таком графе, менеджер понимает, какие задачи нельзя задерживать ни на день, чтобы не сорвать общие сроки проекта.
