Как работает топологическая сортировка и как найти цикл в ориентированном графе?

Топологическая сортировка упорядочивает вершины ориентированного графа так, что каждое ребро `u → v` идёт слева направо; она существует тогда и только тогда, когда в графе нет циклов, и строится за `O(V + E)`.

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

Берём вершины с нулевой входящей степенью, «удаляем» их рёбра, повторяем. Реализация — массив входящих степеней indeg и очередь. Если обработано меньше V вершин — оставшиеся лежат на цикле или достижимы из него.

DFS с тремя цветами

• Белый — не посещена, серый — в текущем стеке рекурсии, чёрный — обработана.
• Ребро в серую вершину — обратное ребро, то есть цикл.
• Порядок — вершины в обратном порядке выхода из DFS.
• Двух цветов в орграфе мало: ребро в чёрную вершину (поперечное) — не цикл.

Применение

Порядок сборки в make/Bazel, установка зависимостей в пакетных менеджерах, DAG задач в Airflow, пересчёт формул в таблицах. Порядок неоднозначен; лексикографически минимальный даёт очередь с приоритетом вместо обычной — O(E + V log V).

Коротко для собеседования

Топологический порядок есть только у графа без циклов, а строят его алгоритмом Кана по входящим степеням или DFS по времени выхода. Оба способа попутно находят цикл: у Кана остаются необработанные вершины, в DFS встречается ребро в серую вершину, а сам цикл восстанавливают по родителям.