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

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

• Порядок топологической сортировки — порядок убывания времени выхода из вершины.
• Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).
• Время работы O(V + E).

vector<vector<int>> graph(vertexCount);
vector<bool> visited(vertexCount);
vector<int> order;

void dfs(int v) {
    visited[v] = 1;
    for (int to : graph[v])
        if (!visited[to])
            dfs(to);
    order.push_back(v);
}

for (int v = 0; v < vertexCount; v++)
    if (!visited[v])
        dfs(v);
reverse(order.begin(), order.end());

Алгоритм Кана

• Пока в графе остались вершины, находим любой исток, добавляем его к ответу и удаляем из графа вместе со всеми исходящими рёбрами.
• Данный алгоритм, в отличие от предыдущего, позволяет найти лексикографически минимальную топологическую сортировку.
• Время работы O(VlogV + E).

vector<vector<int>> graph(vertexCount);

vector<int> inDegree(vertexCount);
for (int v = 0; v < vertexCount; v++)
    for (int to : graph[v])
        inDegree[to]++;

set<pair<int, int>> q;
for (int v = 0; v < vertexCount; v++)
    q.insert({ inDegree[v], v });

vector<int> order;
while (!q.empty()) {
    int v = q.begin()->second;
    q.erase(q.begin());

    order.push_back(v);

    for (int to : graph[v]) {
        q.erase({ inDegree[to], to });
        inDegree[to]--;
        q.insert({ inDegree[to], to });
    }
}

Ссылки

Теория:

• e-maxx.ru — Топологическая сортировка
• neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки
• brestprog.by — Топологическая сортировка
• algorithmica.org — Продвинутый DFS
• usaco.guide — Topological Sort
• Калинин П. Топологическая сортировка
• Лахно А. Поиск в глубину и его применение
• algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs

Демонстрация:

• VisuAlgo — Graph Traversal

Код:

• codelibrary/cpp/graphs/dfs/topological_sort.cpp
• algs4/Topological.java

Задачи:

• Timus #1022 — Генеалогическое дерево
• Codeforces #100070.B — Топологическая сортировка
• UVa #11060 — Beverages