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

Topological sort упорядочивает directed acyclic graph так, чтобы dependency появилась раньше node, которому она нужна. Kahn algorithm удаляет zero-indegree nodes; DFS может дать reverse finishing order. Это часто встречается в course scheduling, build systems, migration ordering и task planning.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Интервьюеры ожидают cycle detection: если выдали не все nodes, valid topological order не существует.

Типовые ошибки: Topological sort применим только к directed acyclic graphs. Осторожно с edge direction, потому что reversal prerequisite edges меняет смысл indegree.

Чеклист:

• Постройте directed edges.
• Отслеживайте indegrees или DFS colors.
• Выведите все nodes.
• Ясно сообщайте о cycles.