无向图中的循环

Question

给定具有n个顶点（| V | = n）的无向图G =（V，E），您如何查找它是否包含O（n）的循环？

Answer 1

实际上，深度优先（或实际上广度优先）搜索还不够。您需要一个复杂得多的算法。

例如，假设有一个图，它的节点为{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）才会引发异常。

Answer 2

一个没有周期的连通无向图G是一棵树！任何一棵树都恰好具有n − 1条边，因此我们可以简单地遍历图的边列表并计算边。如果我们计算n − 1个边，则返回“是”，但是如果到达第n个边，则返回“否”。这需要O（n）时间，因为我们最多查看n个边。

但是，如果图形未连接，那么我们将不得不使用DFS。我们可以遍历这些边，如果有任何未探索的边通向被访问的顶点，则它具有循环。