给出一个算法,用它来确定一个给定的无向图G=(V,E)中是否包含一个回路。所给出的算法的运行时间为O(V),这一时间独立于|E|
分析
当DFS(深度优先遍历)时, 如果没有向后边(Back Edge), 则无向图无环.
(1) 如果含有向后边, 则无向图存在环.
(2) 如果没有向后边, 根据书中Theorem 22.10 , 无向图只有树边(Tree Edge). 因此, 图是无环的.
所以, 可以使用DFS : 如果发现向后边, 则无向图存在环.
Time: O(V). (非O(V+E))
如果已经查看了 |V| 条边. 则一定看到了向后边. 因为 (根据书中Theorem B.2) 在无环(无向图)中, |E| <= |V| - 1.
解答:我们都知道对于一个无向图而言,如果它能表示成一棵树,那么它一定没有回路,并且有|E|=|V|-1,如果在这个树上添加一条边,那么就构成了回路,如果在这个树中去掉一个边就成了森林(注意:如果只是限定|E|<|V|-1它不一定是森林,它当中可能存在无向连通子图)。
对于这个题目我们可以用DFS来做,每当访问当前节点的邻接表时,如果存在某个邻接的元素已被标记为访问状态,且这个元素不是当前元素的父节点,那么这个图就是存在回路的。总的时间代价是O(|E|+|V|),因为E<=|V|-1(如果|E|>|V|-1根据无向图的性质,那么这个无向图一定存在回路),所以O(|E|+|V|)=O(|V|)