判断图是否有环

系统管理员 2022-05-16 04:47 301阅读 0赞

总结一下判断图是否有环的所有方法，先只给出描述，后面有时间之后给出代码实现。

**一、无向图**

**方法1、**

我们知道对于环1-2-3-4-1，每个节点的度都是2，基于此我们有如下算法（这是类似于有向图的拓扑排序）：

1.  求出图中所有顶点的度，
2.  删除图中所有度<=1的顶点以及与该顶点相关的边，把与这些边相关的顶点的度减一
3.  如果还有度<=1的顶点重复步骤2
4.  最后如果还存在未被删除的顶点，则表示有环；否则没有环

但是可以首先判断边数如果大于顶点数-1，那肯定是有环的，如果没有环路，则该图必然是k棵树 k>=1。根据树的性质，边的数目m = n-k。k>=1，所以：m<n

**方法2、**

根据刚刚方法1最后的分析，可以详细一点来说

首先遍历一遍，判断图分为几部分（假定为P部分，即图有 P 个连通分量），对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1，只要有一个满足 边数 > 结点数－1，原图就有环，将P个连通分量的不等式相加，就得到：

P1:E1=M1-1

P2:E2=M2-1

...

PN:EN>MN-1

也即所有边数(E) > 所有结点数(M) - 连通分量个数(P)  
即： E + P > M 所以只要判断结果 E + P > M 就表示原图有环，否则无环.

**方法3、**

DFS，判断有没有后向边，关于图边的类型看[这里][Link 1]

图中的一个节点，根据其C\[N\]的值，有三种状态：

0，此节点没有被访问过

\-1，被访问过至少1次，其后代节点正在被访问中

1，其后代节点都被访问过。

按照这样的假设，当按照DFS进行搜索时，碰到一个节点时有三种可能：

1、如果C\[V\]=0，这是一个新的节点，不做处理

2、如果C\[V\]=-1，说明是在访问该节点的后代的过程中访问到该节点本身，则图中有环。

3、如果C\[V\]=1，类似于2的推导，没有环。 在程序中加上一些特殊的处理，即可以找出图中有几个环，并记录每个环的路径

这个方法也适用于有向图，这里其实可以简单一些的。

**方法4、**

BFS，首先通过广度遍历（BFS）访问图的所有点，对于每个点，都检测和已访问过的点是否有边（除了和它连接的上层节点），如果有边，说明有回路（有环）。如果对于每个点，都没有和已访问过的点有边，说明从该点出发的当前图没有回路（无环）。如果从任意点开始的BFS，以上操作均说明无回路，才能说明没有回路。

**二、有向图**

**方法1、**

拓扑排序，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：1.每个顶点出现且只出现一次。2.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。做法：

1.从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。  
2.从图中删除该顶点和所有以它为起点的有向边。  
3.重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

**方法2、**

DFS同无向图，其实可以用更简单的DFS，即只用标记一次即可

**方法3、**

这个好像不太行，方法有点扯，但是道理是这样讲，实现起来还是用上面两个。强联通子图，Strongly Connected Components，我们可以回忆一下强连通子图的概念，就是说对于一个图的某个子图，该子图中的任意u->v,必有v->u，则这是一个强连通子图。这个限定正好是环的概念。所以我想，通过寻找图的强连通子图的方法应该可以找出一个图中到底有没有环、有几个环。 关于连通图和其他一些图的部分概念可以看[这里][Link 2]

[Link 1]: https://blog.csdn.net/yimingsilence/article/details/81714199
[Link 2]: https://blog.csdn.net/yimingsilence/article/details/80004565