美文网首页
拓扑排序

拓扑排序

作者: 文景大大 | 来源:发表于2020-12-06 22:04 被阅读0次

一、拓扑排序的使用场景

拓扑排序主要是用于在一个DAG(有向无环图)中将所有的顶点按照依赖顺序关系构造成一个线性序列。

  • 有依赖关系的源文件编译顺序确定;
  • 穿衣服的顺序确定;
  • 存在先修课和后修课依赖关系时,课程顺序的安排;

拓扑排序后的线性序列不止有一种情况适合问题的解,即存在多解的情况。

二、拓扑排序及其适用范围

排序算法都是作用做特定的数据结构上的,分析以上的问题,我们发现,这些问题都可以抽象为一个有向无环图。那么问题就转化成了,如何在一个有向无环图上实现拓扑排序。

2.1 Kahn算法

  • 如果p先于n执行,那么就表示为p指向n;
  • 为所有顶点都初始化如上这种依赖关系,最终形成一个有向无环图(如何判断无环下面会说到);
  • 找到入度为0的顶点,该顶点表示没有其它任何步骤先于它执行;
  • 将如上入度为0的顶点从图中删除,并记录到序列中,同时循环执行上一个步骤;
  • 直至所有顶点都记录到序列中,那么该序列就是一个拓扑排序后的序列;

2.2 DFS算法

即深度优先搜索遍历算法,这个在讲这种数据结构的时候有详细地说过,此处不再赘述。只不过DFS输出的序列正好也是符合拓扑排序的,因此也可以作为拓扑排序的一种解法。

2.3 适用范围

凡是需要通过局部顺序来推导全局顺序的,一般都可以使用拓扑排序来解决。但是要求,图中不能有环,否则就不能使用。那么如何判断图中是否有环呢。

如果我们使用Kahn算法,如果最后输出序列中的顶点个数,少于实际图中的个数,则说明图中还剩下入度不是0的顶点,从而说明了图中存在环。

相关文章

网友评论

      本文标题:拓扑排序

      本文链接:https://www.haomeiwen.com/subject/lopawktx.html