- 摄像头
什么是拓扑排序?
- 2025-7-2 1:43:15 @
本讨论 专门 讲解 何为 拓扑排序
本题题解: https://hydro.ac/p/luogu-P2712/solution/68641f28345cc6899b2b6f31
什么是拓扑排序?
是一类典型的图上无权问题 拓扑排序是对有向无环图(DAG, Directed Acyclic Graph)的所有顶点的一种线性排序,使得对于图中的每一条有向边 (u, v),u 在排序中总是位于 v 的前面。如果图中存在环,则无法进行拓扑排序。
例子
无环
比如你期末数学考的非常好,考了0分,你妈高兴的就要拿扫把抽你(别介意,仅为讲解~)
事件A(你考了0分) 事件B(你妈要打你) 事件先后顺序是 事件A -> 事件B 对吧? 对于有先后关系的,可以用图表示 例如1要在2前 可以从2建一个入度(单向边,从1指到2) 这样你只有访问到1才能访问到2 保证 1前2后 以此类推
有环
还是刚刚的例子 你妈高兴的要打你,但是你要喝可乐 事件A 你要喝可乐,喝完你妈才能打你 事件B 你妈要先打你,打完再喝
就有 事件A <-> 事件B 两件事无法排序了?
如上述关系的在图中称为 环 这叫做 相互依赖
那该怎么写?
基本思路:
1.当然先建图啦!
谁在前就谁向另一项连边 示例: (全部都是 A -> B)
//文件头省略哈
const int maxn = 1000 + 10; // 规定图范围
vector<int> G[maxn]; //此处中括号表示动态数组内的单独数组,类似于二维数组
int ru[maxn]; //记录每个点的入度;
// 省略中间 直击主题
// 假设我们输入了一组数据 a,b,要求 a 在 b 前
G[a].push_back(b); // a的出度(有向边) 出向b
ru[b]++; // b的入度加1;
2.开始
这个特性与queue相似,所以用queue实现较为容易
//那肯定先枚举ru数组内 看有没有0的,如果有0,说明他是第一个元素,加入queue内
queue<int> que;
for(int i=1;i<=ml;i++){
if(ru[i] == 0){
que.push(i);
}
}
//这样就得到第一个数啦
3.删边与完善
//既然得到了开头,那就继续处理啦
while(!que.empty()){ //队列不空就证明还有不是环的成员
int now = que.front(); //取队首
que.pop(); //弹出
for(auto it : G[now]){ //枚举这个弹出元素的出度
ru[it]--; //这个元素弹掉了,那原本入度包含这个元素的元素入度就要减1嘛
if(ru[it] == 0){ //判断,入度为0证明下一个开头是他
que.push(it); //入队
}
}
}
写法总结
关键点解析 入度(inDegree):指向该节点的边数量
入度为0的节点可以作为拓扑排序的起点
算法流程:
不断移除入度为0的节点
更新剩余节点的入度
重复直到所有节点被处理或发现环
环检测:
如果最终结果包含的节点数 < 总节点数 → 存在环
因为环中的节点入度永远不会降为0
时间复杂度:O(V+E)
每个节点和边只被处理一次
此说明仅为拓扑入门,若有疑问/错误,可以指出
2 comments
-
NameGod LV 6 @ 2025-7-7 22:27:18
强!
-
2025-7-4 9:03:32@
目前还没有评论...
- 1
Information
- ID
- 6746
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 3
- Tags
- (None)
- # Submissions
- 28
- Accepted
- 5
- Uploaded By