判断有向图有环

拓扑排序
如果能够用拓扑排序完成对图中所有节点的排序的话，就说明这个图中没有环，而如果不能完成，则说明有环。^[1]

• 深度优先算法 1->2->4->5->3->5 会误判为有环

• 广度优先算法 1->2->3->4->5->5 会误判为有环

  
  image.png

拓扑排序

image.png

[1] 判断一个有向图是否有环