如何判断图中有闭环

---

无向图

1. 利用拓扑排序结合顶点的度：

• 求出所有顶点的度

• 删除所有度<=1的点（叶节点），然后将邻点的度-1。

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

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

  
  image.png

2. 利用DFS看是否能访问到源点。

---

有向图

1. 拓扑排序+顶点的入度：

• 计算所有顶点入度，将入度=0的放入栈中

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

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

  
  image.png

2. DFS老办法。