Skip to content

Latest commit

 

History

History
19 lines (11 loc) · 653 Bytes

TopologicalSorting.md

File metadata and controls

19 lines (11 loc) · 653 Bytes

拓扑排序

拓扑排序 - OI Wiki

作用

对于有向无环图(DAG),将所有节点排序,使得排在前面的前面的节点不依赖后面的节点

具体应用:

  1. 可以用来判断图中是否有环
  2. 还可以用来判断图是否是一条链

Kahn 算法

维护一个集合 S,用于存放入度为 0 的点,每次任意取一个顶点(可以随便取),加入到结果 result 中,同时更新 S。最终得到的 result 就是拓扑排序结果。

如果此时还剩下边,就说明原图有还。

核心是代码的核心是,是维持一个入度为 0 的顶点。