定义

对于一个 有向无环图（DAG），其拓扑排序是将所有节点排成一个线性序列，使得对于每一条有向边 (u, v)，u 在序列中都排在 v 的前面。

一个 DAG 的拓扑排序可能不唯一。

一个直观的理解：如果将图看作一组”先后依赖关系”（如课程的先修关系），拓扑排序就是一种合法的执行顺序。

判定

一个有向图存在拓扑排序，当且仅当它是 DAG（即无环）。

证明

充分性：若图无环，则必定存在入度为 0 的点（否则可以沿边一直走，经过 n + 1 个点后必定有重复，产生环）。不断删去入度为 0 的点即可构造拓扑序。

必要性：若图有环，设环上节点为 v1 → v2 → ⋯ → vk → v1。在拓扑序中，v1 必须在 v2 前，v2 在 v3 前，……，vk 在 v1 前。这与 v1 在 v2 前矛盾。故有环时不存在拓扑排序。

证毕。

Kahn 算法（BFS）

例题：洛谷 B3644 【模板】拓扑排序 / 家谱树。

算法流程

  1. 统计每个节点的入度 degi。
  2. 将所有入度为 0 的节点加入队列。
  3. 每次从队列中取出一个节点 u，将其加入拓扑序。
  4. 遍历 u 的所有出边 (u, v)，将 v 的入度减 1。若 v 的入度变为 0，则将其加入队列。
  5. 重复直到队列为空。

若最终拓扑序的长度为 n，则图是 DAG；否则图中有环。

时间复杂度

每个节点入队出队恰好一次，每条边被遍历一次，时间复杂度 O(n + m)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>

const int N = 1e5 + 10;
int n, m, deg[N];
std::vector<int> G[N], topo;

bool topoSort() {
  std::queue<int> q;
  for (int i = 1; i <= n; ++i)
    if (!deg[i]) q.push(i);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    topo.push_back(u);
    for (int v : G[u])
      if (--deg[v] == 0) q.push(v);
  }
  return (int)topo.size() == n;
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m;
  for (int i = 0, u, v; i < m; ++i) {
    std::cin >> u >> v;
    G[u].push_back(v);
    ++deg[v];
  }
  if (topoSort()) {
    for (int x : topo) std::cout << x << ' ';
    std::cout << '\n';
  }
  std::cout.flush();
  return 0;
}

DFS 实现

也可以使用 DFS 求拓扑排序。对每个未访问的节点进行 DFS，在回溯时将节点加入栈中。最后栈中从顶到底的顺序就是拓扑序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int vis[N];
std::vector<int> topo;
bool hasCycle;

void dfs(int u) {
  vis[u] = 1; // 正在访问
  for (int v : G[u]) {
    if (vis[v] == 1) { hasCycle = true; return; } // 访问到正在栈中的节点，有环
    if (!vis[v]) dfs(v);
    if (hasCycle) return;
  }
  vis[u] = 2; // 访问完成
  topo.push_back(u);
}

最后将 topo 数组翻转即可。

DFS 版本可以同时判环：如果在 DFS 过程中遇到一个标记为”正在访问”的节点，说明存在后向边，即图中有环。

时间复杂度同样是 O(n + m)。

应用

DAG 上 DP

在 DAG 上做 DP 时，通常需要按拓扑序进行转移，以保证转移所依赖的状态已经计算完毕。

例如，求 DAG 上从 s 到 t 的最长路：

fv = max(u, v) ∈ E{fu + w(u, v)}

按拓扑序从前到后计算即可，时间复杂度 O(n + m)。

判断有向图是否有环

拓扑排序是判断有向图是否有环的经典方法：如果能完成拓扑排序（所有节点都被处理），则无环；否则有环。

字典序最小的拓扑序

如果要求字典序最小的拓扑排序，只需将 BFS 中的普通队列换成小根堆（优先队列）即可。

1
2
3
4
5
6
7
8
9
10
11
12
bool topoSort() {
  std::priority_queue<int, std::vector<int>, std::greater<int>> q;
  for (int i = 1; i <= n; ++i)
    if (!deg[i]) q.push(i);
  while (!q.empty()) {
    int u = q.top(); q.pop();
    topo.push_back(u);
    for (int v : G[u])
      if (--deg[v] == 0) q.push(v);
  }
  return (int)topo.size() == n;
}

此时时间复杂度为 O((n + m)log n)。