基本思路
把每个任务画成一个节点,把每条规则“A 在 B 之前”画成从 A 到 B 的箭头。拓扑顺序是所有节点排成的一行,其中每个箭头都指向右边。它叫排序,是因为它把东西排好顺序;但和给数字排序不同,它只需遵守箭头:没有箭头链相连的节点,谁先谁后都可以。
什么时候不可能
如果箭头形成环,比如 A 在 B 之前、B 在 C 之前、C 在 A 之前,那么 A 就必须排在自己前面。所以拓扑顺序恰好在图中没有有向环时存在。这样的图叫有向无环图(DAG)。下面两种方法在有环时都会找到环,因此也很适合用来检测环。
一个例子
取箭头 A → C、B → C、B → D、C → E 和 D → E。Kahn 算法统计入边:A 和 B 都没有,所以 A 先放,然后是 B。删除 B 的箭头后,C 和 D 变为就绪,接着放置它们,最后是 E:顺序为 A, B, C, D, E。DFS 方法先访问 A,然后 C,然后 E;E 最先完成,然后是 C,然后是 A,每个都放到最前面。接着它访问 B 和 D,它们完成后放在更前面:顺序为 B, D, A, C, E。两个顺序都正确。
Kahn 还是 DFS?
Kahn 算法由 Arthur Kahn 于 1962 年发表,它从前往后工作:它总是知道哪些任务现在可以开始,这适合调度,而且可以按任何规则在就绪任务中挑选,比如按字母顺序。DFS 方法由 Robert Tarjan 于 1976 年推广,它从末端往回工作,只需要一次深度优先搜索。两者所需的时间都随节点数加边数增长。
用途
make 等构建工具先编译一个文件所依赖的文件,再编译它。包管理器按依赖顺序安装库。电子表格先计算公式用到的单元格,再重新计算这个单元格。大学检查先修课程能否满足,编译器安排指令顺序,数据管道在输入就绪后才运行每一步。Unix 命令 tsort 本身就做拓扑排序。
动手探索
打开应用,按“单步”。箭头表明哪个节点必须排在哪个之前。使用 Kahn 算法时,每个节点上的数字是它剩余的入边数,就绪的节点为蓝色。使用 DFS 方法时,蓝色节点正在访问中,绿色节点已放置。顺序在图下方的一行中增长。勾选“添加环”,看两种方法如何发现不存在顺序。
常见问题
这里的“拓扑”是什么意思?
这个名字来自拓扑学,它研究事物如何相连,而不是它们的确切形状。顺序只取决于哪些节点由箭头相连,而与它们画在哪里无关。
没有顺序时,怎样找到环?
DFS 方法会直接显示:指向仍在访问中的节点的那条边,加上正在访问的节点组成的路径,就是环。Kahn 算法只告诉你哪些节点卡住了;在这些节点中搜索就能找到环。
能在有效顺序中选择特定的一个吗?
可以。在 Kahn 算法中,有多个就绪节点时,挑你喜欢的那个,比如标签最小或最紧急的任务。使用优先队列可以得到按字母顺序最靠前的顺序。
拓扑排序如何用于最短路径?
在有向无环图上,按拓扑顺序松弛每个节点的边,只需一遍就能求出从起点出发的所有最短路径,即使有负权边也可以,比 Dijkstra 算法或 Bellman–Ford 算法更快。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试拓扑排序