如何实现广度优先搜索遍历？ [英] How to implement Breadth-first search traversal?

问题描述

我不能清楚地了解如何使用队列来实现广度优先搜索。

I can't clearly understand how to implement breadth first search using a queue.

这就是我理解的：

 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
}

让我错过了这里？

so what am i missing out here?

推荐答案

正如评论所说，你错误地认为，每个国家都有，可以从它能够生成2个状态。

As stated in the comments, you wrongly assume that each state has exactly 2 states that can be generated from it.

正确的算法是：

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 

抵免维基百科

这篇关于如何实现广度优先搜索遍历？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！