无向图
- 利用拓扑排序结合顶点的度:
-
求出所有顶点的度
-
删除所有度<=1的点(叶节点),然后将邻点的度-1。
-
重复以上步骤直到没有符合条件的顶点为止。
-
若发现有未被删除顶点说明有环,如下图:
image.png
- 利用DFS看是否能访问到源点。
有向图
- 拓扑排序+顶点的入度:
-
计算所有顶点入度,将入度=0的放入栈中
-
如果pop栈中元素并将邻点-1后有新的入度为0的点,则push进栈
-
栈空后如果还有顶点未入栈的则说明有环,如下图:
image.png
- DFS老办法。
网友评论