无向图中的循环

给定具有n个顶点(| V | = n)的无向图G =(V,E),如何找到它是否包含O(n)中的循环？

1> Rafał Dowgir..：

---

我认为深度优先搜索解决了它.如果未探测的边缘导致之前访问过的节点,则该图形包含一个循环.这个条件也使它成为O(n),因为你可以探索最大的n个边而不将其设置为true或没有未探测的边.

---

但是,如果你*标记*每个节点,它肯定是O(n).

---

@Sky它是另一种方式 - 它只适用于*无向*图形.

---

如果你去广泛的第一个搜索路径,然后是一个未探测的边缘,导致之前"发现"的节点,那么该图包含一个循环.BTW,IIRC图算法的运行时通常用V和E来描述.

---

这个答案是不正确的.进行简单的深度优先搜索并不足以找到一个循环.可以在DFS中多次访问节点而不存在循环.

2> 小智..：

---

实际上,深度优先(或实际上广度优先)搜索还不够.你需要一个更复杂的算法.

例如,假设存在具有节点{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

然后运行访问(root_node)将抛出异常,当且仅当存在循环时(最初所有节点应为白色).

---

明确地说:dfs对于无向图是足够的:[*"当且仅当深度优先搜索(DFS)找到指向已经访问过的顶点(后边缘)的边时,无向图才有周期"*](http://en.wikipedia.org/wiki/Cycle_(graph_theory)#Cycle_detection)

---

第2行的if语句始终为false(检查第7行的if语句)

---

@JFSebastian另一种表达方式是，在* any *图中，*无向*或*有向*，如果存在循环，则存在后沿。只是在无向图中，所有边缘都是“树”边缘或“后”边缘，而在有向图中，边缘也可以是CLRS语言中的“向前”或“交叉”边缘。因此，简单的DFS足以满足无向图的需要，而对于有向图则不足够（我们需要另外跟踪所谓的“灰色”节点，或者至少跟踪它们的发现/完成时间）。

3> Ashish Pani..：

---

没有周期的连通无向图G是树!任何树都有n - 1个边,因此我们可以简单地遍历图的边列表并计算边.如果我们计算n - 1个边,那么我们返回"是",但如果我们到达第n个边,那么我们返回"否".这需要O(n)时间,因为我们最多看n个边缘.

但如果图形未连接,那么我们将不得不使用DFS.我们可以遍历边缘,如果任何未探测的边缘导致访问的顶点,那么它具有循环.

---

问题没有指出已知图形已连接,因此仅计算边缘将不起作用.

4> 小智..：

---

您可以使用DFS解决它.时间复杂度:O(n)

该算法的本质是,如果连通的组件/图形不包含循环,它将永远是一个树.见这里是为了证明

让我们假设图没有循环,即它是一棵树.如果我们看一棵树,一个节点的每个边缘:

1.到达它的唯一父母,就在它上面一层.

2.或到达其下方一层的孩子.

因此,如果一个节点有任何其他边缘不属于上述两个边缘,它显然会将节点连接到除其父节点之外的其祖先之一.这将形成一个循环.

既然事实清楚了,你所要做的就是为图形运行一个DFS(考虑到你的图形是连接的,否则对所有未访问的顶点都是这样),如果你找到了一个VISITED的节点的邻居而不是它的父母,然后我的朋友图中有一个CYCLE,你就完成了.

您可以通过在为邻居执行DFS时将父项作为参数传递来跟踪父项.由于您只需要检查最多n个边,因此时间复杂度为O(n).

希望答案有所帮助.

5> 小智..：

---

顺便说一句,如果你碰巧知道它是连接的,那么它只是一棵树(因此没有循环),当且仅当|E|=|V|-1.当然那不是少量的信息:)