如何判断图有环

淡淡的烟草味﹌ 2022-06-14 04:57 217阅读 0赞

转自：https://www.douban.com/note/310835413/

1. 无向图  
  
如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。  
n算法：  
     第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。  
  
     第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。  
  
     如果最后还有未删除顶点，则存在环，否则没有环。  
  
n算法分析：  
     由于有m条边，n个顶点。  
  
     i)如果m>=n，则根据图论知识可直接判断存在环路。（证明：如果没有环路，则该图必然是k棵树 k>=1。根据树的性质，边的数目m = n-k。k>=1，所以：m<n）  
  
     ii)如果m<n 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。这两种操作的总数不会超过m+n。由于m<n，所以算法复杂度为O(n)。  
  
注：  
     该方法，算法复杂度不止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的推导，没有环。 在程序中加上一些特殊的处理，即可以找出图中有几个环，并记录每个环的路径