Топологическая сортировка — это упорядочивание вершин ориентированного ациклического графа (DAG), при котором для каждого ребра (u, v) вершина u идёт перед вершиной v в отсортированном списке.
Применяется для:
- планирования задач с зависимостями (например, сборка проектов),
- определения порядка выполнения инструкций,
- сериализации данных.
Алгоритмы:
- На основе поиска в глубину (DFS).
- На основе подсчёта входящих рёбер (алгоритм Кана).
Пример: если задача A зависит от B, то B будет раньше A в отсортированном списке.
Понадобилось мне тут граф зависимостей реализовать. В комментах выложу получившийся php класс.
