美文网首页
如何判断图中有闭环

如何判断图中有闭环

作者: 小幸运Q | 来源:发表于2018-09-18 00:36 被阅读48次

无向图

  1. 利用拓扑排序结合顶点的度:
  • 求出所有顶点的度

  • 删除所有度<=1的点(叶节点),然后将邻点的度-1。

  • 重复以上步骤直到没有符合条件的顶点为止。

  • 若发现有未被删除顶点说明有环,如下图:


    image.png
  1. 利用DFS看是否能访问到源点。

有向图

  1. 拓扑排序+顶点的入度:
  • 计算所有顶点入度,将入度=0的放入栈中

  • 如果pop栈中元素并将邻点-1后有新的入度为0的点,则push进栈

  • 栈空后如果还有顶点未入栈的则说明有环,如下图:


    image.png
  1. DFS老办法。

相关文章

网友评论

      本文标题:如何判断图中有闭环

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