拓扑排序简记（看了点赞呗）
2026-03-22 17:38:44
发布于：北京
12阅读
0回复
0点赞
拓扑排序定义
一个有向无环图(DAG) 𝐺=(𝑉,𝐸) 的拓扑排序指它的顶点的一个特殊的线性顺序
它满足：如果边 (𝑢,𝑣)∈𝐸，则顶点 𝑢 一定排在 𝑣 的前面
关键：一个顶点有入边，则说明它有依赖事件需要先执行。
举个例子：
像入度:0 的洗衣服、烧水、买菜，都没有依赖的事件，
换句话说，它们可以直接执行。
像入度:1 的晾衣服、煮咖啡，它们都有 1 个入度，需要
先完成前的事情，若前面事情完成了，代表入度为 0。
拓扑排序步骤
- 1，初始化一个队列。作用：记录入度为0的顶点入队
- 2，遍历整个图，将其中入度为0的顶点入队
- 3，当队列非空，重复以下操作
-
- a，取出队首元素，将其插入当前得到的拓扑序列的末端
-
- b，遍历它的每条出边，删除，如果对应的终点的入度变为0，则将它入队
- 4，返回得到的拓扑序列
代码模板：（例题）
#include <bits/stdc++.h>
using namespace std;
// 常量定义：最大节点数
const int maxn = 1e2 + 9;
// 全局变量
bool vis[maxn]; // 标记节点是否被访问（是否在拓扑排序中）
int deg[maxn]; // 节点的入度
vector<int> ve[maxn];// 邻接表存储图
int main() {
int n;
cin >> n;
// 读入图的边信息，构建邻接表并统计入度
for (int i = 0; i < n; i++) {
int x, m;
cin >> x >> m;
while (m--) {
int y;
cin >> y;
ve[x].push_back(y); // 添加边 x -> y
deg[y]++; // y的入度加1
}
}
// 拓扑排序：初始化队列，将入度为0的节点入队
queue<int> q;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
vis[i] = 1;
q.push(i);
}
}
// 执行拓扑排序
while (!q.empty()) {
int r = q.front();
q.pop();
// 遍历当前节点的所有邻接节点
for (int i = 0; i < ve[r].size(); i++) {
int y = ve[r][i];
// 邻接节点入度减1，若入度为0则入队
if (--deg[y] == 0) {
vis[y] = 1;
q.push(y);
}
}
}
// 统计未被访问的节点数（即存在环的节点数）
int num = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
num++;
}
}
// 输出结果：有环则输出环中节点数，无环则输出YES
if (num) {
cout << num;
} else {
cout << "YES";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
// 常量定义：最大节点数（适配 2e5 规模的图）
const int maxn = 2e5 + 9;
// 全局变量
vector<int> ve[maxn]; // 邻接表存储有向图
int deg[maxn]; // 存储每个节点的入度
int main() {
// n: 节点数，m: 边数
int n, m;
cin >> n >> m;
// 读入 m 条有向边，构建邻接表并统计入度
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
ve[u].push_back(v); // 添加有向边 u -> v
deg[v]++; // 节点 v 的入度加 1
}
// 优先队列（小根堆）：保证拓扑排序结果字典序最小
priority_queue<int, vector<int>, greater<int>> q;
// 初始化：将所有入度为 0 的节点加入优先队列
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
q.push(i);
}
}
vector<int> ans; // 存储拓扑排序的结果
// 执行拓扑排序（字典序最小）
while (!q.empty()) {
int r = q.top(); // 取出当前入度为0的最小节点
q.pop();
ans.push_back(r); // 加入拓扑排序结果
// 遍历当前节点的所有邻接节点
for (int y : ve[r]) {
// 邻接节点入度减1，若入度变为0则加入队列
if (--deg[y] == 0) {
q.push(y);
}
}
}
// 判断是否存在环，并输出结果
if (ans.size() != n) {
cout << "has circle"; // 结果长度不足，说明有环
} else {
// 无环，输出字典序最小的拓扑排序结果
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
}
return 0;
}
难度提高的拓扑排序往往需要结合其他算法，例如递推，动态规划等
拓扑排序
- 可以判断是否有环
- 可以得到完成若干个任务的拓扑序列
有帮助，赞一个