1. 什么是拓扑排序？

拓扑排序针对的是 有向无环图（DAG，Directed Acyclic Graph）。

假设有这样的依赖关系：

A → B
A → C
B → D
C → D

箭头 A → B 可以理解为：

想做 B，必须先做 A。

那么一种合法的执行顺序就是：

A → B → C → D

也可以是：

A → C → B → D

这两个都是正确的。

所以，拓扑排序就是把图中的所有节点排成一个线性顺序，使得对于每一条边 u → v，u 都出现在 v 前面。

注意：拓扑排序通常 不唯一。

2. 为什么必须是“有向无环图”？

比如：

A → B
↑   ↓
└── C

也就是：

A → B
B → C
C → A

A 要在 B 前面，B 要在 C 前面，C 又要在 A 前面。

这是不可能的。

一个有向图存在拓扑排序，当且仅当它是 DAG（Directed Acyclic Graph）。

这个性质非常重要，算法题会反过来利用拓扑排序 判断图中是否存在环。

3. 最经典的方法：入度法（Kahn 算法）

Kahn 算法的核心流程可以概括为：

  1. 统计所有节点的入度。
  2. 把所有 入度为 0 的节点放入队列。
  3. 每次从队列取出一个节点，将它加入拓扑序列。
  4. 删除这个节点发出的所有边，也就是让它指向的节点入度 -1。
  5. 如果某个节点入度变成 0，就加入队列。
  6. 重复直到队列为空。

例如：

A → B
A → C
B → D
C → D

初始入度：

A = 0
B = 1
C = 1
D = 2

所以首先只有：

队列：[A]

取出 A：

结果：[A]

B 入度：1 → 0
C 入度：1 → 0

于是：

队列：[B, C]

假设取 B：

结果：[A, B]

D 入度：2 → 1

再取 C：

结果：[A, B, C]

D 入度：1 → 0

然后 D 入队，最终：

[A, B, C, D]

这就是一个拓扑序列

4. Kahn 算法代码

以常见的邻接表写法为例：

bool TopologicalSort(ALGraph& G) {
    int indegree[MAXV] = {0};

    //遍历领接表，获得每个节点的入度
    for (int i = 0; i < G.vexnum; ++i) {
        for (ArcNode* p = G.vertices[i].first; p != nullptr; p = p->next) {
            indegree[p->adjvex]++;
        }
    }

    std::queue<int> q;

    //将入度为0的节点压入队列
    for (int i = 0; i < G.vexnum; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0;

    //循环对每个度为0的节点进行操作
    //直到队列为空
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        count++;

        std::cout << v << " "; 

        //队列中的节点，让其指向的节点入度-1
        //如果某个节点入度为0，压入队列中
        for (ArcNode* p = G.vertices[v].first; p != nullptr; p = p->next) {
            int k = p->adjvex;

            indegree[k]--;

            if (indegree[k] == 0) {
                q.push(k);
            }
        }
    }

    return count == G.vexnum;
}

为什么 count != G.vexnum 就说明有环？

这是拓扑排序里非常经典的判断。

考虑：

A → B → C
    ↑   ↓
    └───┘

其中：

B → C
C → B

B 和 C 形成了一个环。

那么：

B 入度 > 0
C 入度 > 0

即使其他节点都处理完了，B 和 C 的入度也永远不可能变成 0。

于是队列最终会空掉，但是还有节点没有处理。

因此：

count < G.vexnum

说明图中存在环

反过来，如果：

count == G.vexnum

说明所有节点都成功被处理，因此图是 DAG。

5. 时间复杂度

V = 节点数
E = 边数

每个节点最多处理一次，每条边最多处理一次，所以时间复杂度是：O(V+E)O(V+E) 拓扑排序的额外空间复杂度是 O(V)O(V)
如果把输入图的邻接表存储也算上，则总空间复杂度是 O(V+E)O(V+E)。

今天学校开始正式上课了，
让人头疼的老师，
考勤抓的严，课堂作业多。
课上根本没法集中注意力学习，学不进去。
我的学习计划迎来重大挑战😡。

对可恶的上课勇敢说不 甘奈