判断有向图有环
2019-01-20 本文已影响0人
RoyTien
拓扑排序
如果能够用拓扑排序完成对图中所有节点的排序的话,就说明这个图中没有环,而如果不能完成,则说明有环。[1]
- 深度优先算法 1->2->4->5->3->5 会误判为有环
-
广度优先算法 1->2->3->4->5->5 会误判为有环
image.png
拓扑排序
image.png
[1] 判断一个有向图是否有环
拓扑排序
如果能够用拓扑排序完成对图中所有节点的排序的话,就说明这个图中没有环,而如果不能完成,则说明有环。[1]
广度优先算法 1->2->3->4->5->5 会误判为有环
拓扑排序
[1] 判断一个有向图是否有环