拓扑排序 Topological-Sort

• 对一个有向无环图G进行

  拓扑排序， 是将G中所有

  顶点排成一个线性序列，

  使 对 于 图 中 任 意 弧

  <u, v>∈E， u在序列中出

  现在v之前

 

有向无环图

Directed Acyclic Graph， DAG

 

拓扑排序保证所有的有向边在序列中都是从左边

结点指向右边结点；如果图是有回路的， 就不可

能存在这样的线性序列

 

　　　　　　拓扑排序算法 – 非递归版

• 一开始，对那些入度为0的点而言。

  不存在什么点必须排在它们前面，

  可以随便排(可以排在最前面)，后

  面的点受他们的限制。

• 每次删去一个入度为0的点以及这

  个点出发的所有边。

 

　　　　　　另一种拓扑排序算法

• 使用dfs算法。

• 每当访问完一个结点，就把这个结点

  加入到拓扑排序结果序列中。

• 注意这个顺序是逆序的。

• 因此，我们从后往前加 topo[n--] = u

 

• 欧拉回路算法也用到了类似的思想。

 

 

---

 

如果你不开心，那我就把右边这个帅傻子分享给你吧， 你看，他这么好看，跟个zz一样看着你，你还伤心吗？ 真的！这照片盯上他五秒钟就想笑了。 一切都会过去的。 时间时间会给你答案2333