2

有向グラフで BFS アルゴリズムを使用してサイクルを検出しようとしています。サイクルを検出するための私の主なアイデアは次のとおりです。BFS は各ノード (およびエッジ) を 1 回だけ訪問するため、既に訪問したノードに再び遭遇した場合。循環を引き起こします。ただし、私のコードはサイクルを見つけることもあれば、見つけないこともあります。

ウィキペディアから変更した擬似コードは次のとおりです。

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

実装の問題は、グラフが接続されていると想定していることです。しかし現実には、2 つの接続された部分を持つグラフを扱う場合があるため、最初からv他の部分に入ることはありません。問題を解決するには、接続されていない可能性のあるサブグラフを識別する方法を見つける必要があります。ウィキペディアhttp://en.wikipedia.org/wiki/Topological_sorting#Algorithmsでいくつかの提案を見つけることができます。

 S ← Set of all nodes with no incoming edges

編集：

実際に行うことができる簡単な変更はv、エンキューする代わりに、すべてのノードをダイクストラ スタイルでエンキューすることです。そうすれば、常に自分のサイクルを見つけることができます。またt、メソッド シグネチャの一部ではないため、どこから取得していますか?

于 2013-01-25T13:09:35.983 に答える
0

指定したアルゴリズムは、サイクルが存在しない場合でも、サイクルの存在を報告する場合があります。12 行目では、t の隣に u があります。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 に答える