美文网首页
拓扑排序(Topological Sorting/Orderin

拓扑排序(Topological Sorting/Orderin

作者: 程序猪小羊 | 来源:发表于2018-02-11 06:33 被阅读26次

本文系转载,感谢原文作者。
(原文地址:https://songlee24.github.io/2015/05/07/topological-sorting/
侵删。

一、什么是拓扑排序

在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:

  1. 每个顶点出现且只出现一次。
  2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。

另外,拓扑排序还可以采用 深度优先搜索(DFS)的思想来实现,详见《topological sorting via DFS》。

相关文章

网友评论

      本文标题:拓扑排序(Topological Sorting/Orderin

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