判断图有无环_【转】判断一个图是否有环无向图有向图

Myth丶恋晨 2023-01-10 05:13 237阅读 0赞

无向图：

法1：

如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。

n算法：

第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。

第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。

如果最后还有未删除顶点，则存在环，否则没有环。

n算法分析：

由于有m条边，n个顶点。如果m>=n，则根据图论知识可直接判断存在环路。

(证明：如果没有环路，则该图必然是k棵树 k>=1。根据树的性质，边的数目m = n-k。k>=1，所以：m

如果m

另：

该方法，算法复杂度不止O(V)，首先初始时刻统计所有顶点的度的时候，复杂度为(V + E)，即使在后来的循环中E>=V，这样算法的复杂度也只能为O(V + E)。其次，在每次循环时，删除度为1的顶点，那么就必须将与这个顶点相连的点的度减一，并且执行delete node from list\[list\[node\]\]，这里查找的复杂度为list\[list\[node\]\]的长度，只有这样才能保证当degree\[i\]=1时，list\[i\]里面只有一个点。这样最差的复杂度就为O(EV)了。

法2：

DFS搜索图，图中的边只可能是树边或反向边，一旦发现反向边，则表明存在环。该算法的复杂度为O(V)。

有向图：

主要有深度优先和拓扑排序2中方法

1、拓扑排序，如果能够用拓扑排序完成对图中所有节点的排序的话，就说明这个图中没有环，而如果不能完成，则说明有环。

2、可以用Strongly Connected Components来做，我们可以回忆一下强连通子图的概念，就是说对于一个图的某个子图，该子图中的任意u->v,必有v->u，则这是一个强连通子图。这个限定正好是环的概念。所以我想，通过寻找图的强连通子图的方法应该可以找出一个图中到底有没有环、有几个环。

3、就是用一个改进的DFS

刚看到这个问题的时候，我想单纯用DFS就可以解决问题了。但细想一下，是不能够的。如果题目给出的是一个无向图，那么OK，DFS是可以解决的。但无向图得不出正确结果的。比如：A->B,A->C->B,我们用DFS来处理这个图，我们会得出它有环，但其实没有。

我们可以对DFS稍加变化，来解决这个问题。解决的方法如下：

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

0，此节点没有被访问过

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

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

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

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

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

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

发表评论取消回复

表情：

评论列表（有 0 条评论，237人围观）

还没有评论，来说两句吧...

相关阅读

相关【图】使用邻接表判断有向图和无向图中是否有环（Java 实现）

需求判断给定的图中是否有环本文研究有向图及无向图两种情况分析 1、当图中边的数量大于节点数量时，必然存在环； 2、当图中边的数量小于等于节点是，

骑猪看日落/ 2023年10月08日 22:48/ 0 赞/ 161 阅读

相关判断有向图是否有环

题目：[LeetCode207. Course Schedule][]。在这里我提供三种解法：解法一：寻找从入度为0的点，删掉从它们出发的边。持续进行会构造新的入度

叁歲伎倆/ 2023年10月04日 11:56/ 0 赞/ 110 阅读

相关判断图有无环_【转】判断一个图是否有环无向图有向图

无向图：法1：如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。 n算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它

Myth丶恋晨/ 2023年01月10日 05:13/ 0 赞/ 238 阅读

相关判断有向图是否有环及拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)

旧城等待，/ 2022年08月03日 13:39/ 0 赞/ 274 阅读

相关判断一个有向图是否有环

转自：http://blog.csdn.net/panhe1992/article/details/8366466 Description 给出一个有向图，判

今天药忘吃喽~/ 2022年06月14日 04:57/ 0 赞/ 260 阅读

相关有向无环图VS树

有向无环图VS树： -------------------- 前言: Big-man在看着 [《终极算法》][Link 1] 的时候，突然一个很要好的朋友（

迈不过友情╰/ 2022年06月08日 09:08/ 0 赞/ 420 阅读

相关判断图是否有环

总结一下判断图是否有环的所有方法，先只给出描述，后面有时间之后给出代码实现。一、无向图方法1、我们知道对于环1-2-3-4-1，每个节点的度都是2，基于此我们有如

系统管理员/ 2022年05月16日 04:47/ 0 赞/ 397 阅读

相关判断一个有向图是否有环

Description 给出一个有向图，判断图中是否存在回路。 Input 第 1 行：输入图的顶点个数 N （ 1 ≤ N ≤ 2,500 ）和 C （图

- 日理万妓/ 2022年04月22日 06:50/ 0 赞/ 322 阅读

相关 DAG有向无环图

参考 https://ctolib.com/yueyunyue-liteflow.html DAG有向无环图：https://blog.csdn.net/ya

淡淡的烟草味﹌/ 2022年01月26日 06:05/ 0 赞/ 382 阅读

相关计划应当是一个有向无环图

按照时间片来做计划是一个反人性的策略，时间片本来就是计算机多任务处理用的，用到人身上，不就是强行让人在不同人物之间来回切换吗；机器上下文切换快，但是人的上下文切换可没有那么快。

桃扇骨/ 2021年12月24日 15:57/ 0 赞/ 341 阅读