拓扑排序
定义
拓扑排序的英文名是 Topological sorting。
拓扑排序要解决的问题是给一个图的所有节点排序。
我们可以拿大学选课的例子来描述这个过程,比如学习大学课程中有:单变量微积分,线性代数,离散数学概述,概率论与统计学概述,语言基础,算法导论,机器学习。当我们想要学习 算法导论 的时候,就必须先学会 离散数学概述 和 概率论与统计学概述,不然在课堂就会听的一脸懵逼。当然还有一个更加前的课程 单变量微积分。这些课程就相当于几个顶点
但是如果某一天排课的老师打瞌睡了,说想要学习 算法导论,还得先学 机器学习,而 机器学习 的前置课程又是 算法导论,然后你就一万脸懵逼了,我到底应该先学哪一个?当然我们在这里不考虑什么同时学几个课程的情况。在这里,算法导论 和 机器学习 间就出现了一个环,显然你现在没办法弄清楚你需要学什么了,于是你也没办法进行拓扑排序了。因而如果有向图中存在环路,那么我们就没办法进行 拓扑排序 了。
因此我们可以说 在一个 DAG(有向无环图) 中,我们将图中的顶点以线性方式进行排序,使得对于任何的顶点
还有给定一个 DAG,如果从
拓扑排序的目标是将所有节点排序,使得排在前面的节点不能依赖于排在后面的节点。
Kahn 算法
过程
初始状态下,集合
每次从
不断重复以上过程,直到集合
首先看来自 Wikipedia 的伪代码
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
代码的核心是维持一个入度为 0 的顶点的集合。
可以参考该图
对其排序的结果就是:2 -> 8 -> 0 -> 3 -> 7 -> 1 -> 5 -> 6 -> 9 -> 4 -> 11 -> 10 -> 12
时间复杂度
假设这个图
因而总的时间复杂度就有
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
DFS 算法
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
时间复杂度:
合理性证明
考虑一个图,删掉某个入度为
应用
拓扑排序可以用来判断图中是否有环,
还可以用来判断图是否是一条链。
求字典序最大/最小的拓扑排序
将 Kahn 算法中的队列替换成最大堆/最小堆实现的优先队列即可,此时总的时间复杂度为
习题
CF 1385E:需要通过拓扑排序构造。
Luogu P1347: 拓扑排序模板。
参考
- 离散数学及其应用。ISBN:9787111555391
- https://blog.csdn.net/dm_vincent/article/details/7714519
- Topological sorting,https://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=854351542
本页面最近更新:2023/2/18 07:57:07,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:aofall, CCXXXI, ChungZH, CoelacanthusHex, countercurrent-time, cquptEthan, Enter-tainer, evrmji, fearlessxjdx, H-J-Granger, H-Shen, iamtwz, Ir1d, Marcythm, mcendu, Menci, NachtgeistW, ouuan, Persdre, Prevalence, Ravenclaw-OIer, shuzhouliu, SukkaW, Tiphereth-A, TrisolarisHD, Walker30360, william-song-shy, Xeonacid, zhb2000
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用