拓扑排序

yyycj · 2025-08-06 21:14:03 · 算法·理论

拓扑排序，是 Toposort 的音译。

对于一个有向无环图，如果顶点 u 能到达顶点 v，那么在序列中 u 在 v 的前面，最后由 n 个顶点形成的任意一种（因为可能由多个序列均满足情况）序列叫做拓扑序列，求拓扑序列的过程叫拓扑排序。

由于只有有向无环图才有拓扑序列，所以有向无环图也叫做拓扑图。

由于顶点 u 能到达顶点 v，那么在序列中 u 在 v 的前面，所以入度为 0 的顶点已经处于序列的最前面，接下来就是 bfs 的过程了，每次从队列顶取出顶点时存放进一个序列里，接着让这个顶点能到达的点的入度都减 1，如果某个点的入度为 0，就让它加入队列，最后就能得到一种拓扑序列。

代码：

int head = 1, tail = 0;
for (int i = 1; i <= n; i++) {
    if (d[i] == 0) q[++tail] = i;
}
while (head <= tail) {
    int u = q[head++];
    for (int i : edge[u]) {
        if (--d[i] == 0) q[++tail] = i;
    }
}