当前位置：首页 > news >正文

【学习笔记】拓扑排序

news 2026/5/12 0:09:43

[TOC]

$OI$-拓扑排序

什么是拓扑排序

拓扑排序（Topological sorting）要解决的问题是如何给一个有向无环图的所有节点排序．

换句话说，就是对于一条边，使得$u$在$v$前。这样的线性序列称为满足拓扑次序的序列。

我们可以举个例子：

比如$CZC$的游戏中有「魔法屏障」和「能量盾」还有「再生护甲」

规则是这样的：必须先得获得「能量盾」再得获得「魔法屏障」最后获得「再生护甲」

「能量盾」↓
「魔法屏障」↓
「再生护甲」

小脑萎缩

但有一天$CZC$开发时大脑旋转小脑萎缩，说：”要想获得「魔法屏障」先得获得「再生护甲」“

「能量盾」↓
「魔法屏障」↓  ↑
「再生护甲」

显然$Gamer$们现在没办法弄清楚自己需要先打什么了(っ °Д °;)っ

也就没办法进行拓扑排序了．因为如果有向图中存在环路，那么我们就没办法进行拓扑排序

性质们

所以我们可以说🧐：只有在 DAG(有向无环图) 时，才能跑拓扑🤓

同理，我们可以发现下性质：

还有给定一个 DAG，如果从 $i$ 到 $j$ 有边，则认为 $j$ 依赖于 $i$．如果 $i$ 到$j$ 有路径（$i$ 可达 $j$），则称 $j$ 间接依赖于 $i$ ．

拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点．

总结一下：

DAG特性：只有有向无环图才能进行拓扑排序
依赖关系：
- 直接依赖：如果从i到j有边，则j直接依赖于i
- 间接依赖：如果i到j有路径，则j间接依赖于i
排序目标：使排在前面的节点不依赖于排在后面的节点

现在，我们可以愉快的思考代码实现了

Kahn算法

思考new算法

假设你是Kahn

你要思考一个新算法！！！

Think。。

他说：使得排在前面的节点不能依赖于排在后面的节点

我们就直接看没有被指过的：

1 → 2
↓
3 → 4

显然，选 $1$

 _
|1| → 2-↓3 → 4

接下来我们就可以向外拓展，并删掉这条边。

Q&A

有没有一种可能，他有没指过的(っ °Д °;)っ

没有的，兄弟，没有的。

因为我们是DAG(有向无环图) 呀！！！

如果真有，大家就会直接想到一个图：

1 ← 2
↓   ↑
3 → 4

这不就又环了吗！！

算法流程

Kahn算法的核心思想是不断选择图中入度为0的节点，输出后将其从图中移除。

初始化一个队列，将所有入度为0的节点入队
当队列不为空时： a. 取出队首节点u并输出 b. 移除u的所有出边，即对于u指向的每个节点v，将v的入度减1 c. 如果v的入度变为0，则将v入队
如果输出的节点数等于总节点数，则排序成功；否则说明图中存在环

停下想一下(´･ω･)?

重复上面两步，直到所有顶点都输出，拓扑排序完成，或者图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成，陷入死锁．

模板

int n, m;
vector<int> G[MAXN];
int in[MAXN];  // 存储每个结点的入度bool toposort() 
{vector<int> L;queue<int> S;for (int i = 1; i <= n; i++)if (in[i] == 0) S.push(i);while (!S.empty()) {int u = S.front();S.pop();L.push_back(u);for (auto v : G[u]) {if (--in[v] == 0) {S.push(v);}}}if (L.size() == n) {for (auto i : L) cout << i << ' ';return true;}return false;
}

复杂度

遍历图：$O(E)$

检查每一条边$O(V)$

总共：$O(E + V)$

空间 $O(1)$

DFS

实际上就是递归版

（代码来源于OI-Wiki）

using Graph = vector<vector<int>>;  // 邻接表struct TopoSort {enum class Status : uint8_t { to_visit, visiting, visited };const Graph& graph;const int n;vector<Status> status;vector<int> order;vector<int>::reverse_iterator it;TopoSort(const Graph& graph): graph(graph),n(graph.size()),status(n, Status::to_visit),order(n),it(order.rbegin()) {}bool sort() {for (int i = 0; i < n; ++i) {if (status[i] == Status::to_visit && !dfs(i)) return false;}return true;}bool dfs(const int u) {status[u] = Status::visiting;for (const int v : graph[u]) {if (status[v] == Status::visiting) return false;if (status[v] == Status::to_visit && !dfs(v)) return false;}status[u] = Status::visited;*it++ = u;return true;}
};