algorithm - 幅優先探索トラバーサルを実装する方法は？

Question

キューを使用して幅優先探索を実装する方法が明確に理解できません。

これは私が理解したことです：

 create queue Q
 enqueue root onto Q

while( !Q.empty() )
{
  node t = Q.deque();
  if(t is the goal we're seeking)
      return t;
  enqueue   t->leftchild
  enqueue   t->rightchild
}

だから私はここで何を逃しているのですか？

Answer 1

コメントに記載されているように、各状態には、そこから生成できる状態が正確に 2 つあると誤って想定しています。

正しいアルゴリズムは次のとおりです。

BFS(G,v):
      create a queue Q
      enqueue v onto Q
      mark v
      while Q is not empty:
          t ← Q.dequeue()
          if t is what we are looking for:
              return t
          for all edges (t,u) in G do
             if u is not marked:
                  mark u
                  enqueue u onto Q 

ウィキペディアのクレジット