algorithm - 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

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

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