logo标签列表

无向图中的循环

algorithmgraphgraph-theory
71

给定一个无向图G=(V, E)，其中有n个顶点（|V| = n），如何在O(n)的时间复杂度内确定它是否包含循环？

17个回答
71

我认为深度优先搜索可以解决这个问题。如果一条未被探索的边引导到一个之前访问过的节点，则图包含一个循环。该条件还使其具有O(n)时间复杂度，因为您最多可以探索n条边而不将其设置为true或留下没有未探索的边。

6
如果你选择广度优先搜索，那么如果有一条未探索的边通向已经被“发现”的节点，则该图包含一个环。顺便提一下，我记得图算法的运行时间通常是用V和E来描述的。 - oz10
1
嗯...如果你不小心的话，这可能会演变成一个O(n^2)算法，对吧？如果你通过将所有节点保留在链表中（新节点添加到末尾）来检查先前是否访问过某个节点，那么你将不得不在每次检查时扫描节点列表（扫描本身就是O(n)）。因此 - O(n^2)。 - Mark Brittingham
1
这个条件也被称为反向边。在运行DFS之后，如果结果DFS树包含任何反向边（指向树中祖先的边），则知道存在一个循环。这对于有向图也适用。 - rahulmehta95
4
这个答案是不正确的。简单的深度优先搜索并不足以找到一个循环。在深度优先搜索中，有可能会多次访问一个节点，但却不存在循环。 - Sky
8
@Sky 这个情况正好相反，它只在无向图中有效。 - Rafał Dowgird
显示剩余7条评论
35

实际上，深度优先（或广度优先）搜索并不足够。您需要一个稍微复杂一些的算法。

例如，假设有一个节点为{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)将抛出异常。

5
第2行的if语句始终为false（请查看第7行的if语句）。 - Rontogiannis Aristofanis
2
对于一个有向图，运行拓扑搜索。如果成功：没有环。否则：存在环。 - Alaa M.
14
明确地说，对于无向图，深度优先搜索（DFS）已足够：当且仅当深度优先搜索找到指向已经访问过的顶点的边时（即一条反向边），无向图才存在环。参考链接：http://en.wikipedia.org/wiki/Cycle_(graph_theory)#Cycle_detection - jfs
4
换个说法，对于任何图形，无向的或有向的，只要存在环，则必然存在返祖边。只是在无向图中，所有边都是“树”边或“返祖”边，而在有向图中，边也可以是“前向”或“跨越”边，用CLRS的语言来说。因此，对于无向图，简单的深度优先搜索就足够了，但对于有向图则不行（我们还需要额外跟踪所谓的“灰色”节点，或者至少它们的发现/完成时间）。 - jme
2
"并得出结论存在一个循环 - 而实际上并不存在。" - 什么？显然是存在一个循环的。 - Dominik
显示剩余3条评论
19
一个没有环的、连通的无向图G是一棵树！任何一棵树都恰好有n-1条边，因此我们可以简单地遍历图的边列表并计算边数。如果我们计算了n-1条边，则返回“是”，但如果我们达到第n条边，则返回“否”。这需要O(n)时间，因为我们最多查看n条边。
但如果图不是连通的，则我们必须使用深度优先搜索DFS。我们可以遍历边缘，如果任何未经探索的边缘导致已访问的顶点，则它具有循环。
但是如果图中有平行边怎么办？在这种情况下，边的数量将大于n-1，但仍然没有环。我有什么遗漏吗？ - thebenman
1
平行边本身就构成了一个环。 - Ashish Pani
是的。不知怎么就完全错过了。谢谢！ - thebenman
4
问题没有明确说明这张图是连通的，所以仅仅计算边的数量是行不通的。 - sagittarian
15

你可以使用深度优先搜索算法解决它。时间复杂度：O(n)

该算法的本质是，如果一个连通组件/图不包含环，它将始终是一棵树。请看这里的证明

让我们假设图没有环，即它是一棵树。 如果我们看一棵树，每个节点的边：

1.要么到达它唯一的父节点，即比它高一层。

2.或到达它的子节点，即比它低一层。

所以，如果一个节点有任何其他不在上述两种情况中的边，它显然会将该节点连接到除其父节点之外的其它祖先节点。这将形成一个环。

现在，事实已经清楚了，你只需要对图运行DFS（考虑到你的图是连通的，否则对所有未访问的顶点进行DFS），并且IF（如果）你找到一个节点的邻居被访问而且不是它的父节点，那么朋友们，图中就有一个环，你完成了。

你可以通过在为其邻居执行DFS时将父节点作为参数传递来跟踪父节点。 由于你最多只需要检查n条边，所以时间复杂度是O(n)。

希望这个答案有所帮助。

1
这是对这颗树的一个好的观察。这意味着，如果你只想要一个是/否的答案，你可以计算每个连通分量中边的数量，并将其与(n-1)进行比较，其中n = 连通分量中或整个连通图中节点的数量。 - Tomasz Gandor
谢谢。确实那是观察到的。 - mb1994
7

顺便说一下，如果您知道它是连接的，那么当且仅当|E|=|V|-1时，它就是一棵树（因此没有循环）。当然，这不是一个小量的信息 :)

4
答案是，实际上是广度优先搜索（或深度优先搜索，这并不重要）。细节在于分析。
那么，这个算法有多快呢？
首先，假设图中没有环。边的数量为O(V)，图是一片森林，目标达成。
现在，假设图中有环，且你的搜索算法将在第一个环中完成并报告成功。该图是无向的，因此当算法检查一条边时，只有两种可能性：要么它已经访问了该边的另一端，要么它已经访问了该边的另一端，这条边就会闭合成一个圆。一旦它看到了边的另一个顶点，那个顶点就被“检查”了，因此只有O(V)次这样的操作。第二种情况只会在整个算法运行期间出现一次。
2
一个简单的深度优先搜索可以检查给定的无向图是否有环。

这是相同的C++代码。

上述代码中使用的思想是：

如果发现/访问了一个已经发现/访问的节点，并且不是父节点，则表示存在一个环。

这也可以解释为（由@Rafał Dowgird提到）

如果未探索的边导致到达之前访问过的节点，则图包含一个环。

2

使用DFS算法进行遍历，条件是（parent != next node） 让我们看一下代码，然后理解其中的含义：

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的邻接矩阵中的下一个顶点，所以下一个顶点1也是2的父节点。因此，在这个DFS方法中，不会检测到立即父节点的循环。因此，代码可以正常工作。请注意保留HTML标签。
1

如果DFS没有返回回溯边，则无向图是无环的（即森林）。 由于回溯边是连接顶点u到深度优先树中祖先v的边(u, v)，因此没有回溯边意味着只有树边，所以没有环。 因此，我们可以简单地运行DFS。如果发现回溯边，则存在环。其复杂度为O(V)而不是O(E + V)。这是因为如果存在回溯边，则在看到|V|个不同的边之前必须将其找到。这是因为在无环（无向）森林中，|E|≤|V|+1。

1

我认为假设图是连通的可以很方便。因此，您可以使用上面展示的证明，运行时间为O（|V|）。如果不是，则|E|>|V|。 提醒：DFS的运行时间为O（|V|+|E|）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接