2

我正在尝试在有向图中使用 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

我错过了什么？

4

4 回答 4

4

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

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

于 2013-01-24T19:31:41.493 回答
0

即使不存在循环，您给出的算法也可能会报告存在循环。在第 12 行，你我们有 u 与 t 相邻。BFS 树中 t的父节点也位于它的邻接表中。 So, line 13 might return false even when no cycle exist because a parent of t is marked and is a part of t's adjacency list.

所以，我认为这个算法会报告一个循环，如果它存在，但它也可能会报告一个循环，即使没有循环。

于 2013-03-17T18:55:19.203 回答
0

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

 S ← Set of all nodes with no incoming edges

编辑：

实际上，您可以做的一个简单的改变是代替入队v，将所有节点入队Dijkstra 样式。这样你应该总能找到你的周期。另外你从哪里得到t，因为它不是方法签名的一部分？

于 2013-01-25T13:09:35.983 回答
0

你的算法不会总能找到循环。因为，如果节点v不存在于任何循环中，或者无法从节点v到达循环，那么它将无法工作。我们可以做一些修改。节点数等于n。从每个节点运行一个 bfs。伪代码：

1 create a queue Q
2 create a array visited
3 create a array level
4 set answer = infinity
5 for each node 1 to **n**
6      mark the visited equals to **0**.  
7      clear the **Q**
8      enqueue **v** onto Q
9      visited [ v ] = 1
10     while Q is not empty:
11            t <- Q.dequeue()
12            for all edges e in G.adjacentEdges(t) do
13            u <- G.adjacentVertex(t,e)          
14            if u is not visited:
15                 visited [ u ] = 1
16                 level [ u ] = level [ t ] + 1;
17                 enqueue u onto Q
18            else:
19                 answer = min( answer , level [ t ] + level [ u ] + 1 )

完成算法后，您将得到整个图中的最小循环作为答案。

于 2020-07-01T04:51:01.113 回答