无向图中的循环
给定一个有n个顶点（| V | = n ）的无向图G =（ V ， E ），你如何find它是否包含O （ n ）中的一个循环？
我认为深度优先search解决了这个问题。 如果未探索的边缘导致之前访问的节点，则该graphics包含循环。 这个条件也使得它成为O（n），因为你可以探索最大的n条边而不需要把它设置为真或者没有未被探索的边。
实际上，深度优先search还是不够的。 你需要一个更复杂的algorithm。
例如，假设存在具有节点{a，b，c，d}和边{（a，b），（b，c），（b，d），（d，c）}的图，其中边，y）是从x到y的边。 （看起来像这样，所有的边都朝下。）
(a) | | (b) / \ (d) | | | \ / (c) 然后做深度优先search可以访问节点a，然后b然后c然后回到c然后访问d，最后再次访问c并得出没有的时候有一个循环。 类似的事情首先发生在广度上。
你需要做的是跟踪你在访问中的哪个节点。 在上面的例子中，当algorithm达到（d）它已经完成访问（c），但不是（a）或（b）。 所以重新访问完成的节点是好的，但访问一个未完成的节点意味着你有一个循环。 通常的做法是将每个节点颜色设为白色（尚未访问），灰色（访问子孙）或黑色（完成访问）。
这里是一些伪代码！
define visit(node n): if n.colour == grey: //if we're still visiting this node or its descendants throw exception("Cycle found") n.colour = grey //to indicate this node is being visited for node child in n.children(): if child.colour == white: //if the child is unexplored visit(child) n.colour = black //to show we're done visiting this node return
那么运行访问（root_node）会抛出一个exception当且仅当有一个循环（最初所有节点应该是白色的）。
对不起，如果你已经知道这一切，它可能是你的意思深入search无论如何，但我希望它有帮助。
没有周期的连通的无向图G是树！ 任何树都有n-1条边，所以我们可以简单地遍历图的边列表并计算边。 如果我们计算n-1条边，那么我们返回“是”，但如果我们到达第n条边，则返回“否”。 这需要O（n）时间，因为我们最多看n个边。
但是，如果graphics没有连接，那么我们将不得不使用DFS。 我们可以遍历边，如果有任何未探索的边通向访问顶点，那么它就会循环。
您可以使用DFS解决它。 时间复杂度：O（n）
该algorithm的本质是，如果一个连接的组件/图不包含一个循环，它将永远是一个树。 看到这里的certificate
让我们假设图没有循环，即它是一棵树。 如果我们看一棵树，每个节点的边：
或者达到它唯一的一个父级，这个级别比它高一级。
2.或到达其下一级的孩子。
所以如果一个节点有其他边缘不在上面描述的两个边界之内，那么它显然会把节点连接到它的父节点以外的祖先之一。 这将形成一个循环。
既然事实是清楚的，你所要做的就是为图表运行一个DFS（考虑到你的graphics是连通的，否则就是为所有未访问的顶点做），如果你find了一个被访问的节点的邻居而不是它的父母，那么我的朋友在图中有一个CYCLE，你就完成了。
您可以通过简单地传递父项作为参数，当您为其邻居做DFS时跟踪父项。 而且由于你只需要最多检查n条边，时间复杂度就是O（n）。
希望答案有帮助。
答案是，广度优先search（或深度优先search，这并不重要）。 细节在于分析。
现在，algorithm有多快？
首先，想象这个图没有周期。 那么边的数量就是O（V），这个图就是森林，达到了目标。
现在，想象一下这个图有周期，你的searchalgorithm将在第一个结束并报告成功。 该图是无向的，因此，当algorithm检查一个边时，只有两种可能性：它或者访问了边的另一端，或者它有，然后，这个边closures一个圆。 一旦它看到边的另一个顶点，那个顶点就被“检查”，所以这些操作只有O（V）。 第二种情况在algorithm运行期间只能达到一次。
顺便说一句，如果你碰巧知道它是连通的，那么只要是|E|=|V|-1 ，那么它就是一棵树（因此没有循环）。 当然这不是less量的信息:)
我相信graphics连接的假设可能是less数。 因此，您可以使用上面显示的certificate，运行时间是O（| V |）。 如果不是，则| E |> | V |。 提醒：DFS的运行时间是O（| V | + | E |） 。
下面是我用C编写的基于DFS的代码，以查明给定graphics是否连接/循环。 在一些样品输出结束。 希望它会有所帮助:)
#include<stdio.h> #include<stdlib.h> /****Global Variables****/ int A[20][20],visited[20],v=0,count=0,n; int seq[20],s=0,connected=1,acyclic=1; /****DFS Function Declaration****/ void DFS(); /****DFSearch Function Declaration****/ void DFSearch(int cur); /****Main Function****/ int main() { int i,j; printf("\nEnter no of Vertices: "); scanf("%d",&n); printf("\nEnter the Adjacency Matrix(1/0):\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&A[i][j]); printf("\nThe Depth First Search Traversal:\n"); DFS(); for(i=1;i<=n;i++) printf("%c,%d\t",'a'+seq[i]-1,i); if(connected && acyclic) printf("\n\nIt is a Connected, Acyclic Graph!"); if(!connected && acyclic) printf("\n\nIt is a Not-Connected, Acyclic Graph!"); if(connected && !acyclic) printf("\n\nGraph is a Connected, Cyclic Graph!"); if(!connected && !acyclic) printf("\n\nIt is a Not-Connected, Cyclic Graph!"); printf("\n\n"); return 0; } /****DFS Function Definition****/ void DFS() { int i; for(i=1;i<=n;i++) if(!visited[i]) { if(i>1) connected=0; DFSearch(i); } } /****DFSearch Function Definition****/ void DFSearch(int cur) { int i,j; visited[cur]=++count; seq[count]=cur; for(i=1;i<count-1;i++) if(A[cur][seq[i]]) acyclic=0; for(i=1;i<=n;i++) if(A[cur][i] && !visited[i]) DFSearch(i); }
/ *示例输出：
majid@majid-K53SC:~/Desktop$ gcc BFS.c majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 10 Enter the Adjacency Matrix(1/0): 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 The Depdth First Search Traversal: a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10 It is a Not-Connected, Cyclic Graph! majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 4 Enter the Adjacency Matrix(1/0): 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1 The Depth First Search Traversal: a,1 c,2 b,3 d,4 It is a Connected, Acyclic Graph! majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 5 Enter the Adjacency Matrix(1/0): 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 The Depth First Search Traversal: a,1 d,2 b,3 c,4 e,5 It is a Not-Connected, Acyclic Graph! */
一个简单的DFS可以检查给定的无向图是否有循环。
这是C ++代码相同。
在上面的代码中使用的想法是：
如果已经发现/访问的节点再次被发现并且不是父节点，那么我们有一个循环。
这也可以解释如下（由@RafałDowgird提到
如果未探索的边缘导致之前访问的节点，则该graphics包含循环。
如果DFS不产生后沿，则无向图是非循环的（即，森林）。 由于后沿是在深度优先树中将顶点u连接到祖先v那些边（ u ， v ），所以没有后边意味着只有树边，所以没有循环。 所以我们可以简单地玩DFS。 如果find一个后沿，就有一个周期。 复杂度是O(V )而不是O(E + V ) 。 因为如果有后端边缘，在看到|V |之前必须先find 明显的边缘。 这是因为在一个非循环（无向）森林中， |E| ≤ |V | + 1 |E| ≤ |V | + 1 |E| ≤ |V | + 1 。
正如其他人所说…深度优先search将解决它。 一般情况下，首先search需要O（V + E），但在这种情况下，您知道该图最多有O（V）个边。 所以你可以简单地运行一个DFS，一旦你看到一个新的边缘增加一个计数器。 当计数器达到V时，您不必继续，因为graphics肯定有一个循环。 显然这需要O（V）。
我相信正确使用DFS也取决于你将如何在代码中表示你的graphics。 例如，假设您使用相邻列表来跟踪相邻节点，并且您的图有2个顶点并且只有一个边：V = {1,2}和E = {（1,2）}。 在这种情况下，从顶点1开始，DFS会将其标记为VISITED，并将其放入队列中。 之后，它将popup顶点2，因为1与2相邻，并且1被访问，DFS会断定有一个循环（这是错误的）。 换句话说，在无向图（1,2）和（2,1）是相同的边，你应该以一种方式编码，使DFS不会考虑它们的不同边。 为每个访问节点保留父节点将有助于处理这种情况。
我最近开始学习图表。 我在java中编写了一段代码，可以确定一个图是否有循环。 我使用DFT来查找图中的周期。 我使用堆栈遍历graphics，而不是recursion。
在高层使用堆栈的DFT在以下步骤中完成
- 访问一个节点
- 如果节点不在访问列表中，则将其添加到列表中并将其推送到堆栈的顶部
- 将堆栈顶部的节点标记为当前节点。
- 对当前节点的每个相邻节点重复上述操作
- 如果所有节点都被访问，则从当前节点popup堆栈
我从Graph的每个节点执行DFT，并且在遍历过程中，如果遇到我之前访问过的顶点，我检查顶点的堆栈深度是否大于1。 我还检查了一个节点是否有自己的边，节点之间是否有多条边。 我原来写的栈版本不是很优雅。 我读了如何使用recursion完成的伪代码，它是整洁的。 这是一个Java实现。 LinkedList数组表示一个graphics。 每个节点和它的相邻顶点分别由数组的索引和每个项目表示
class GFG { Boolean isCyclic(int V, LinkedList<Integer>[] alist) { List<Integer> visited = new ArrayList<Integer>(); for (int i = 0; i < V; i++) { if (!visited.contains(i)) { if (isCyclic(i, alist, visited, -1)) return true; } } return false; } Boolean isCyclic(int vertex, LinkedList<Integer>[] alist, List<Integer> visited, int parent) { visited.add(vertex); for (Iterator<Integer> iterator = alist[vertex].iterator(); iterator.hasNext();) { int element = iterator.next(); if (!visited.contains(element)) { if (isCyclic(element, alist, visited, vertex)) return true; } else if (element != parent) return true; } return false; }
}
没有循环的无向图有| E | <| V | -1。
public boolean hasCycle(Graph g) { int totalEdges = 0; for(Vertex v : g.getVertices()) { totalEdges += v.getNeighbors().size(); } return totalEdges/2 > g.getVertices().size - 1; }
