使用BFS进行循环检测

Question

我试图用BFS算法在有向图中检测循环。我检测周期的主要想法是：由于BFS只访问每个节点（和边缘）一次，如果我再次遇到已访问的节点；它会导致一个循环。然而，我的代码有时会找到循环，有时不会。

我从维基百科修改的伪代码如下：

1  procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t <- Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.adjacentEdges(t) do
12             u <- G.adjacentVertex(t,e)
13             if u is not marked:
14                  mark u
15                  enqueue u onto Q
16             else:
17                  print "Cycle detected!" //since we saw this node before

我错过了什么？

Answer 1

即使不存在循环，您给出的算法也可能报告存在循环。在第12行中，我们有u与t相邻。BFS树中t的父级也位于其邻接列表中<代码>所以，即使不存在循环，第13行也可能返回false，因为t的父级被标记并且是t的邻接列表的一部分

所以，我认为这个算法将报告一个周期，如果它存在的话，但它也可能报告一个周期，即使没有周期。

Answer 2

实现的问题是，它假定图形是连接的。但现实情况是，你可能要处理一个有两个相连部分的图，因此如果你从v开始，你永远不会进入另一部分。要解决您的问题，您需要找到一种方法来识别可能未连接的子图。你可以在维基百科上找到一些建议http://en.wikipedia.org/wiki/Topological_sorting#Algorithms他们谈论的地方

 S ← Set of all nodes with no incoming edges

编辑：

实际上，您可以做的一个简单更改是不要排队v，而是排队所有节点Dijkstra样式。这样您应该始终找到您的周期。此外，您从哪里获得t，因为它不是方法签名的一部分？

Answer 3

您给出的算法可能会在找到循环之前找到目标节点（并因此退出）。

哪个对你更重要：尽快找到目标还是找到周期？如果您根本不关心目标，可以删除算法的该部分。