- 当前
- 就绪或访问中
- 已放置
- 环
拓扑排序
先穿袜子再穿鞋,先打地基再砌墙,先修完一门课再上需要它的课。拓扑排序把有单向边的图的节点排成一行,使每条边都从前指向后。选择 Kahn 算法或 DFS 方法,单步查看顺序如何增长;再添加一个环,看看为什么这时不可能有顺序。 按“播放”观看顺序逐步增长,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。每条边都是单向的,如箭头所示:可以理解为“这个在那个之前”。选择方法:Kahn 算法先放置没有入边的节点,每个节点上的数字是它剩余的入边数;DFS 方法在一个节点之后的所有节点都放置好后,把它放到最前面。图下方的一行是目前的顺序。勾选“添加环”,看看每种方法如何发现环。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。
它是如何运作的
- 选择 Kahn 算法或 DFS 方法。
- 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到任意位置。
- 观察图下方的顺序逐步增长。勾选“添加环”,看看每种方法如何发现环。
Kahn 算法
对每个节点,统计有多少条边指向它。没有入边的节点不依赖任何节点,可以排在最前。放置这样一个节点,并删除它的出边:它们指向的节点入边少了一条,有些会降到零而变为就绪。不断放置就绪节点,直到一个都不剩。如果有些节点始终没有就绪,它们就在环中互相等待,不存在拓扑顺序。
DFS 方法
从每个未访问的节点开始运行深度优先搜索。当从一个节点能到达的所有节点都已完成时,这个节点就完成了,所以必须排在它后面的节点都已放置。把每个完成的节点放到顺序的最前面,得到的顺序就是正确的。如果搜索沿着一条边到达一个仍在其中的节点,这条边就形成了环,同样不存在顺序。
常见问题
什么是拓扑排序?
有向图节点的一种排列,其中每条边都从较前的节点指向较后的节点。如果边表示“必须在之前”,它就是能完成所有任务的一种顺序。
拓扑顺序什么时候存在?
恰好在图中没有有向环时,也就是图为有向无环图(DAG)时。如果有环,环上的每个节点都必须排在自己前面。
拓扑顺序是唯一的吗?
通常不是。只要两个节点之间没有边链相连,谁先都可以,所以一个图可以有许多有效顺序。Kahn 算法和 DFS 方法给出的顺序常常不同。
拓扑排序有多快?
两种方法对每个节点和每条边都只看固定次数,所以工作量随节点数加边数增长。
我的图会被发送到别处吗?
不会。图的生成和排序都在你的浏览器中完成,上次的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器