问题：给出一个算法，用它来确定一个给定的无向图G=(V,E)中是否包含一个回路。所给出的算法的运行时间为O(V)，这一时间独立于|E|

解答：我们都知道对于一个无向图而言，如果它能表示成一棵树，那么它一定没有回路，并且有|E|=|V|-1，如果在这个树上添加一条边，那么就构成了回路，如果在这个树中去掉一个边就成了森林（注意：如果只是限定|E|<|V|-1它不一定是森林，它当中可能存在无向连通子图）。     对于这个题目我们可以用DFS来做，每当访问当前节点的邻接表时，如果存在某个邻接的元素已被标记为访问状态，那么这个图就是存在回路的。总的时间代价是O(|E|+|V|)，因为E<=|V|-1(如果|E|>|V|-1根据无向图的性质，那么这个无向图一定存在回路)，所以O(|E|+|V|)=O(|V|)

来自：http://blog.163.com/kevinlee_2010/

来自：

 

其他思路：

  第一种是类似有向图拓扑排序的思路：（参考有向图判断回路的解答）

        如果存在回路，则必存在一个子图，是一个环。因此该子图中所有顶点入度>=1。

算法： 在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减1，循环直到没有入度为0的定点。如果此时还有未被删除顶点，则必存在环路，否则不存在环路。

 

     无向图则可以转化为： 如果存在回路，则必存在一个子图，是一个环路。因此环路中所有顶点的度>=2。

算法：

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

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

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

算法分析：

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

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

   k>=1，所以：m<n）

如果m<n 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。这两种操作的总数不会超过m+n。由于m<n，所以算法复杂度为O(n)

 

第二种为借助广度优先的策略：

  任选一个顶点进行广度优先搜索。由于广度优先的算法本质就是从一个顶点出发将图按距离该顶点的远近层层展开为树形结构，如果存在某个顶点被访问两次表明树形展开层次结构中存在回边，因此则必存在回路。

  一种比较直接的思路是：为了要判断是否存在环路，需要在每个新近被加入访问队列的顶点上记录下该顶点的上一步的父顶点是哪一个，除了父顶点外其它相关顶点可以加入广度优先算法的队列，并将所有入队顶点的访问次数加一。如果发现访问次数>1的情况，则存在回路。反之，如果算法结束没有访问次数>1的情况则不存在回路。

 

贺司衡同学借鉴MIT教程《Introduction to Algorithms》中广度优先周游图的处理方法：

对每一个元素染色（实际操作可用整数表示）。创建一个队列Q。初始状态将全部元素染成白色。从图中第一个节点（顶点数组中第一个元素），开始广度周游。元素入队染成灰色，出队后染成黑色。例如元素A入队，染成灰色，A出队，染成黑色，邻近节点有三种可能：黑、白、灰。若为黑色节点是深度周游序列之前已访问过的，忽略不管（因而避免了“回访”现象）：若是白色节点则入队，染灰；若有灰色节点表明该节点以存在于队列中，即两个深度优先周游方向的序列将在此汇合，也就说明无向图存在回路。上述三种情况中，有灰色情况则表明有回路，若没有则继续循环直至遍历每个节点，说明没有回路。

                                                             

另外一种思路是： 

对每一个连通子图，以任何一点作为树的根，进行一遍广搜。记节点i的深度为deep(i)，如果一个点u除父节点v外，还存在与之连通的点w，满足deep(w)≤deep(u)，既存在回边，则存在环，时间复杂度o(n)。

 

 

 

第三种方法 

利用图论的知识，即如果存在回路，则至少存在一个连通分量中边的数目m >= 顶点数n。因此，在图的广度或深度周游算法中记录每个连通分量中的顶点数n’，O(n)；统计与这些顶点相关联的边的数目m’如果m’ = n’，则算法结束，存在回路，O(n)。否则不存在回路。