Топологическая сортировка через DFS: почему ответ — это вершины в порядке завершения, развёрнутые?
Реализую топологическую сортировку через DFS (не Кан). В коде вершина добавляется в список после обхода всех её детей, а потом список разворачивается. Не понимаю интуитивно, почему «порядок завершения наоборот» даёт корректный топологический порядок. Можно объяснение/доказательство?
2 ответа
Алгоритм: запускаем DFS; когда вершина закрывается (все её исходящие рёбра обработаны), кладём её в список. В конце разворачиваем список — это топологический порядок.
vector<int> g[N]; vector<bool> used; vector<int> order;
void dfs(int v) {
used[v] = true;
for (int u : g[v]) if (!used[u]) dfs(u);
order.push_back(v); // момент ЗАВЕРШЕНИЯ
}
// for v: if(!used[v]) dfs(v); потом reverse(order)
Почему верно (через времена завершения). Утверждение: для любого ребра u → w время завершения fin[u] > fin[w]. Тогда сортировка по убыванию fin (= развёрнутый порядок добавления) ставит u раньше w для каждого ребра — это и есть определение топологического порядка.
Доказательство утверждения. Рассмотрим момент, когда DFS обрабатывает ребро u→w:
- Если w белая (не посещена) — DFS уходит в w, w закроется внутри обработки u, значит
fin[w] < fin[u]. ✓ - Если w чёрная (уже закрыта) —
fin[w] < fin[u]тривиально (w закрылась раньше). ✓ - Если w серая (на стеке рекурсии) — это значило бы обратное ребро = цикл, но в DAG циклов нет, такого не бывает.
Итак для всякого ребра fin[u] > fin[w], ч.т.д.
Сложность O(V+E), память O(V) (стек рекурсии + список). На больших V — итеративный DFS, чтобы не переполнить стек.
Практическое сравнение с Каном (BFS-версией). DFS-топсорт короче кода и не требует массива входящих степеней, но: (1) использует рекурсию → риск переполнения стека на глубоких графах; (2) детект цикла надо добавлять отдельно (три цвета), тогда как у Кана он бесплатный (order.size() < n).
Ещё нюанс: если нужен лексикографически наименьший топологический порядок, DFS-версия его не даёт «из коробки» — для лексикографического минимума берут Кан с priority_queue вместо очереди. А DFS-порядок зависит от порядка перебора рёбер. Так что выбор Кан vs DFS — это не только про стек, но и про то, какой именно из многих валидных топопорядков вам нужен.