グラフ</p> <p>上BFSトラバーサルについては、単に迅速かつ愚かな質問

Question

をキューから取り出すときに私はBFSのための擬似コードは、このようなかなりのものです多くのサイトで見つけBFSに訪れたとしてノードをマーク：

BFS (Graph, root): 

create empty set S 
create empty queue Q  
add root to S //mark as visited here 
Q.enqueue(root)      
while Q is not empty: 
    current = Q.dequeue() 
    if current is the goal: 
     return current 
    for each node n that is adjacent to current: 
     if n is not in S: 
      add n to S //mark as visited here 
      Q.enqueue(n) 

私はちょうど与えられたノードをマークアップするほうが、後のアプローチでは余分なステップを書く必要があるため、ノードをマークするのではなく、ノードをマークした方が少し簡単です。大きなことではないことは分かっていますが、2つではなく1つの場所でノードを訪問したとマークする方が理にかなっています。より簡潔で、覚えやすく、学習することさえ容易です。

修正版は、ちょうどこのようになります：

BFS (Graph, root): 

create empty set S 
create empty queue Q  
Q.enqueue(root)      
while Q is not empty: 
    current = Q.dequeue() 
    add current to s //just add this and remove the other 2 lines 
    if current is the goal: 
     return current 
    for each node n that is adjacent to current: 
     if n is not in S: 
      Q.enqueue(n) 

私はちょうどない、私の知る限り、これがすべてではトラバーサルの動作を変更するべきではありません知っているように、この変更が正しいかどうかを知りたいですそれ？

Answer 1

デキューした後に訪問したときに頂点をマークするのを待つと、BFSの動作が変更されます。 QとSは次のようになります、各ステップで

   A 
      /\ 
      / \ 
      B  C 
      \ /
       \/
       D 
       /|\ 
      /| \ 
      E F G 

：：次のグラフを考えてみましょう

Q   S 
===== ======= 
{A}  {} 
{B,C} {A} 
{C,D} {A,B} 
{D,D} {A,B,C} // dequeue C - D is not in the visited list, so enqueue D again 

あなたが見ることができるように、私たちは二度キューにDを持っています。 Dの子供たちのすべてもそうで...二回キューに

Q    S 
============= ======== 
{D,E,F,G}  {A,B,C,D} 
{E,F,G,E,F,G} {A,B,C,D} 

を追加しました...とされます。キュー内の2つ以上のノードが同じ（未訪問の）ノードを再度指している場合は、より多くの複製が得られます。

不要な処理に加えて、先行ノードリストを使用してノード間のパスを追跡している場合、または検出順序を記録している場合、期待どおりの結果が得られません。それが問題なのかどうかはもちろん、あなたの特定の問題に左右されます。

明らかに、このシナリオは一般的なグラフでのみ起こりますが、ツリーではありませんが、BFSはグラフアルゴリズムであり、グラフ用とツリー用の2つの異なる実装を暗記するのは、すべてのケースで機能する1つの実装。