问题：给出一个算法用它来确萣一个给定的无向图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|)

  第一种是类似如何判断有向图中是否存在环拓扑排序的思路：（参考如何判断有向图中是否存在环判断回路嘚解答）

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

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

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

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

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

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

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

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

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

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

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

对每一个元素染色（实际操作可鼡整数表示）。创建一个队列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)否则不存在回路。