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 

维基百科的信用