Топологическая сортировка: алгоритм Кана через очередь — как заодно обнаружить цикл?
Нужно отсортировать ориентированный граф топологически. Знаю, что есть алгоритм Кана через входящие степени и очередь. Но что делать, если в графе есть цикл — топологического порядка же не существует? Как Кан сам по себе подсказывает наличие цикла?
2 ответа
Идея Кана: вершины без входящих рёбер можно ставить в начало. Считаем входящие степени indeg, кладём в очередь все вершины с indeg==0, по очереди извлекаем вершину, добавляем в ответ и «удаляем» её рёбра (уменьшаем indeg соседей); кто обнулился — в очередь.
vector<int> kahn(int n, vector<int> g[]) {
vector<int> indeg(n, 0), order;
for (int v = 0; v < n; v++)
for (int u : g[v]) indeg[u]++;
queue<int> q;
for (int v = 0; v < n; v++) if (indeg[v] == 0) q.push(v);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
for (int u : g[v]) if (--indeg[u] == 0) q.push(u);
}
return order; // если order.size() < n -> есть цикл
}
Детектор цикла бесплатно: если в order попало меньше n вершин, значит остались вершины, у которых indeg так и не дошёл до нуля — они образуют цикл (друг друга держат). Так что order.size() != n ⇔ в графе есть ориентированный цикл.
Сложность O(V+E) по времени, O(V) по памяти. Плюс Кана над DFS-версией: не использует рекурсию (нет проблемы со стеком) и легко делать лексикографически минимальный порядок, заменив queue на priority_queue.
Альтернатива — топсорт через DFS, где цикл ловится через три цвета вершины (белый/серый/чёрный). Серый = «в текущем стеке рекурсии»; ребро в серую вершину = обратное ребро = цикл:
int color[N]; // 0=white,1=gray,2=black
vector<int> order;
bool dfs(int v) {
color[v] = 1;
for (int u : g[v]) {
if (color[u] == 1) return false; // нашли цикл
if (color[u] == 0 && !dfs(u)) return false;
}
color[v] = 2;
order.push_back(v);
return true;
}
// затем reverse(order) — это и есть топологический порядок
Ключ: топологический порядок — это вершины в порядке завершения DFS, развёрнутые. И серый цвет даёт детект цикла. O(V+E). Минус против Кана — рекурсия (стек), плюс — не нужна структура indeg.