Алгоритмы

Топологическая сортировка: Порядок зависимостей

Цели урока

Понять задачу топологической сортировки
Реализовать через DFS
Реализовать алгоритм Кана (BFS)
Детектировать циклы

Предварительные знания

DFS: Поиск в глубину

Каждый раз, когда вы запускаете npm install или make, за кулисами работает топологическая сортировка. Она гарантирует, что зависимости собираются в правильном порядке.

Системы сборки (Make, Gradle, Bazel)
Пакетные менеджеры (npm, pip, cargo)
Компиляторы (порядок компиляции модулей)
Spreadsheets (порядок пересчёта формул)

Алгоритм Кана 1962 года и метод через DFS

Топологическая сортировка как явный алгоритм появилась в 1962 году в короткой заметке Артура Кана Topological Sorting of Large Networks в Communications of the ACM. Кан работал с сетевыми моделями проектов вроде PERT, где задачи зависят друг от друга, и нужно выстроить их в выполнимый порядок. Его метод прост и нагляден: находим вершины без входящих рёбер (источники), убираем их, обновляем степени соседей, повторяем. Если в какой-то момент источников нет, а вершины ещё остались, в графе есть цикл, и порядка не существует. Второй способ, через обход в глубину, стал общеизвестен после того, как Роберт Тарьян формализовал DFS-технику в 1970-х: достаточно взять вершины в обратном порядке завершения DFS. Оба работают за O(V + E). Сама идея старше: она неявно присутствовала в анализе сетей PERT и CPM конца 1950-х, разработанном для управления крупными инженерными и военными проектами.

Идея: упорядочить зависимости

**Задача:** даны зависимости между задачами. Нужно найти порядок выполнения, при котором каждая задача выполняется после всех своих зависимостей.

**Требования:**

Граф должен быть **ориентированным** (DAG = Directed Acyclic Graph)
**Нет циклов!** (иначе порядок невозможен)
Если есть ребро u → v, то u должно быть ПЕРЕД v

**Цикл = нет решения.** A зависит от B, B от C, C от A - ни один нельзя выполнить первым!

Граф: A→B, B→C, C→A. Топологическая сортировка:

Алгоритм через DFS

**Идея:** при DFS вершина «закрывается» после всех её потомков. Значит, обратный порядок закрытия - топологический!

Почему результат DFS нужно развернуть (reverse)?

Алгоритм Кана (BFS)

**Альтернатива:** алгоритм Кана. Итеративно убираем вершины без входящих рёбер.

	DFS	Kahn
Подход	Обратный порядок выхода	Удаление источников
Детекция цикла	GRAY→GRAY ребро	len(result) < V
Память	O(V) рекурсия	O(V) очередь
Параллелизация	Сложно	Проще (независимые источники)

Kahn обнаруживает цикл когда:

Применения

**1. Системы сборки (Make, Gradle, npm):**

**2. Планирование задач:**

**3. Компиляторы (порядок инициализации):**

**4. Spreadsheets (пересчёт формул):**

В npm/yarn зависимости образуют цикл. Что произойдёт?