给定一个具有n个顶点 (| V | = n )的无向图G =( V , E ) ，如何确定它是否包含O ( n ) 中的环？
Eran Kampf
问问题
117681 次
17 回答
69
我认为深度优先搜索可以解决它。如果未探索的边指向之前访问过的节点，则该图包含一个循环。此条件也使其成为 O(n)，因为您可以探索最大 n 条边而无需将其设置为 true 或留下没有未探索的边。
于 2009-02-08T21:00:32.940 回答
34
实际上，深度优先（或者实际上是广度优先）搜索还不够。你需要一个更复杂的算法。
例如，假设有一个带有节点 {a,b,c,d} 和边 {(a,b),(b,c),(b,d),(d,c)} 的图，其中边 (x ,y) 是从 x 到 y 的边。（看起来像这样，所有边缘都朝下。）
(a)
|
|
(b)
/ \
(d) |
| |
\ /
(c)
然后进行深度优先搜索可能访问节点（a），然后（b），然后（c），然后回溯到（b），然后访问（d），最后再次访问（c）并得出一个循环 -没有的时候。广度优先也会发生类似的事情。
您需要做的是跟踪您正在访问的节点。在上面的示例中，当算法到达 (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
然后运行 visit(root_node) 当且仅当存在循环时才会抛出异常（最初所有节点都应该是白色的）。
于 2009-02-10T16:07:18.627 回答
16
一个无环的连通无向图 G 是一棵树！任何一棵树都恰好有 n-1 条边，所以我们可以简单地遍历图的边列表并计算边数。如果我们计算 n-1 条边，则返回“是”，但如果我们到达第 n 条边，则返回“否”。这需要 O (n) 时间，因为我们最多查看 n 条边。
但是如果图没有连接，那么我们将不得不使用 DFS。我们可以遍历边缘，如果任何未探索的边缘导致访问的顶点，那么它就有循环。
于 2016-01-04T17:58:33.300 回答
15
您可以使用 DFS 解决它。时间复杂度：O(n)
该算法的本质是，如果连接的组件/图不包含 CYCLE，它将始终是一棵树。见这里为证
让我们假设图没有循环，即它是一棵树。如果我们看一棵树，每个节点都来自一个节点：
1.either 到达它唯一的父级，它比它高一级。
2. 或达到它的子级，它们比它低一级。
因此，如果一个节点有任何其他边不在上述两条边，它显然会将节点连接到它的祖先之一而不是它的父节点。这将形成一个循环。
现在事实已经清楚了，您所要做的就是为图运行 DFS（考虑到您的图是连接的，否则对所有未访问的顶点执行此操作），并且如果您找到已访问的节点的邻居而不是其父母，然后我的朋友在图中有一个循环，你就完成了。
当您对其邻居进行 DFS 时，您可以通过简单地将父级作为参数传递来跟踪父级。而且由于您最多只需要检查n条边，因此时间复杂度将为 O(n)。
希望答案有所帮助。
于 2014-07-11T19:05:42.393 回答
6
顺便说一句，如果你碰巧知道它是连接的，那么它只是一棵树（因此没有循环）当且仅当|E|=|V|-1。当然，这不是少量的信息:)
于 2011-11-21T17:10:39.727 回答
4
答案实际上是广度优先搜索（或深度优先搜索，这并不重要）。细节在于分析。
现在，算法有多快？
首先，假设图形没有循环。那么边的数量是 O(V)，图是一个森林，目标达到了。
现在，假设图形有循环，您的搜索算法将在第一个循环中完成并报告成功。该图是无向的，因此，当算法检查一条边时，只有两种可能性：要么它访问了边的另一端，要么它已经访问了，然后这条边闭合了一个圆。一旦它看到边缘的另一个顶点，那个顶点就会被“检查”，所以这些操作只有 O(V)。在整个算法运行过程中，第二种情况只会出现一次。
于 2009-02-08T21:06:04.157 回答
2
一个简单的 DFS 会检查给定的无向图是否有环。
上面代码中使用的想法是：
如果再次找到已经发现/访问过的节点并且不是父节点，那么我们有一个循环。
这也可以解释如下（@Rafał Dowgird 提到
如果未探索的边指向之前访问过的节点，则该图包含一个循环。
于 2015-06-26T19:26:31.773 回答
2
有条件的 DFS 方法（父！= 下一个节点）让我们看看代码，然后了解发生了什么：
bool Graph::isCyclicUtil(int v, bool visited[], int parent)
{
// Mark the current node as visited
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
// If an adjacent is not visited, then recur for that adjacent
if (!visited[*i])
{
if (isCyclicUtil(*i, visited, v))
return true;
}
// If an adjacent is visited and not parent of current vertex,
// then there is a cycle.
else if (*i != parent)
return true;
}
return false;
}
上面的代码解释了自己，但我会尝试解释一个条件，即 *i != parent 这里如果假设图表是
1--2
然后当我们在 1 到 2 时，2 的父节点变为 1，当我们回到 1 时，因为 1 在 2 的 adj 矩阵中，那么由于下一个顶点 1 也是 2 的父节点，因此不会检测到循环此 DFS 方法中的直接父级。因此代码工作正常
于 2019-11-05T07:05:01.567 回答
1
我相信图是连接的假设很少。因此，您可以使用上面显示的证明，运行时间为 O(|V|)。如果不是，则|E|>|V|。提醒：DFS 的运行时间为O(|V|+|E|)。
于 2010-01-19T23:32:43.610 回答
1
这是我基于 DFS 用 C 语言编写的代码，用于确定给定图是否连通/循环。最后有一些示例输出。希望它会有所帮助:)
#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!
*/
于 2015-05-17T00:36:46.353 回答
1
如果 DFS 不产生后边，则无向图是无环的（即森林）。由于后边是将顶点连接到深度优先树中的祖先
的边（u, ） ，因此没有后边意味着只有树边，因此没有循环。所以我们可以简单地运行 DFS。如果找到后边缘，则有一个循环。复杂性是而不是。因为如果存在后边缘，则必须在看到不同的边缘之前找到它。这是因为在无环（无向）森林中，.vuvO(V)O(E + V)|V||E| ≤ |V| + 1
于 2015-12-16T05:55:08.117 回答
0
正如其他人所提到的......深度优先搜索将解决它。一般来说，深度优先搜索需要 O(V + E)，但在这种情况下，您知道图最多有 O(V) 条边。所以你可以简单地运行一个 DFS，一旦你看到一个新的边缘就增加一个计数器。当计数器达到 V 时，您不必继续，因为图形肯定有一个循环。显然这需要 O(v)。
于 2013-12-24T10:41:10.893 回答
0
我相信正确使用 DFS 还取决于您将如何在代码中表示您的图形。例如，假设您正在使用相邻列表来跟踪相邻节点，并且您的图有 2 个顶点且只有一条边：V={1,2} 和 E={(1,2)}。在这种情况下，从顶点 1 开始，DFS 会将其标记为已访问，并将 2 放入队列中。之后它会弹出顶点 2，由于 1 与 2 相邻，并且 1 被 VISITED，DFS 将得出结论存在一个循环（这是错误的）。换句话说，在无向图中，(1,2) 和 (2,1) 是相同的边，您应该以某种方式对 DFS 进行编码，不要将它们视为不同的边。为每个访问的节点保留父节点将有助于处理这种情况。
于 2014-02-28T10:16:53.487 回答
0
我最近开始研究图表。我用java写了一段代码，可以确定一个图是否有循环。我使用 DFT 在图中找到循环。我使用堆栈而不是递归来遍历图形。
在高级 DFT 中使用堆栈通过以下步骤完成
- 访问节点
- 如果节点不在访问列表中，则将其添加到列表中并将其推送到堆栈顶部
- 将栈顶的节点标记为当前节点。
- 对当前节点的每个相邻节点重复上述操作
- 如果所有节点都被访问过，则将当前节点从堆栈中弹出
我从 Graph 的每个节点执行 DFT，并且在遍历过程中，如果遇到之前访问过的顶点，我会检查该顶点的堆栈深度是否大于 1。我还检查了一个节点是否有自己的边以及节点之间是否有多个边。我最初写的堆栈版本不是很优雅。我阅读了如何使用递归来完成它的伪代码，它很简洁。这是一个java实现。LinkedList 数组表示一个图形。每个节点及其相邻顶点分别由数组和每个项目的索引表示
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;
}
}
于 2017-01-20T06:01:19.377 回答
0
这是 C++ 中一个简单的算法实现，用于检查图是否O(n)及时有循环（n 是图中的顶点数）。我没有在这里展示 Graph 数据结构的实现（为了保持简短的回答）。该算法期望类 Graph 具有公共方法， vector<int> getAdj(int v)该方法返回与 相邻的顶点v并返回顶点int getV()总数。此外，算法假设 Graph 的顶点从 开始编号0 to n - 1。
class CheckCycleUndirectedGraph
{
private:
bool cyclic;
vector<bool> visited;
void depthFirstSearch(const Graph& g, int v, int u) {
visited[v] = true;
for (auto w : g.getAdj(v)) {
if (!visited[w]) {
depthFirstSearch(g, w, v);
}
else if (w != u) {
cyclic = true;
return;
}
}
}
public:
CheckCycleUndirectedGraph(const Graph& g) : cyclic(false) {
visited = vector<bool>(g.getV(), false);
for (int v = 0; v < g.getV(); v++) {
if (!visited[v]){
depthFirstSearch(g, v, v);
if(cyclic)
break;
}
}
}
bool containsCycle() const {
return cyclic;
}
};
请记住，Graph 可能由几个未连接的组件组成，并且组件内部可能存在循环。所示算法也检测此类图中的循环。
于 2020-05-19T20:29:26.650 回答
-2
无环无向图有 |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;
}
于 2012-07-16T18:30:02.307 回答