BFS中的字母顺序

Question

我有麻烦区分BFS与字母顺序和没有它的BFS。

例如，要在此图中查找生成树（从E开始）。

Starting G

添加{E，B}和{E，C}后

T after added EB and EC

我不确定是继续添加{B，F}还是{C，F}。非常感谢你。

Answer 1

我不确定是继续添加{B，F}还是{C，F}。非常感谢你。

那么，答案取决于你在BFS算法队列中添加顶点B和C的顺序。如果你看一下算法：

BFS (G, s)      //Where G is the graph and s is the Source Node

  let Q be queue.
  Q.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.

  mark s as visited.
  while ( Q is not empty)
       //Removing that vertex from queue,whose neighbour will be visited now
       v  =  Q.dequeue( )

      //processing all the neighbours of v  
      for all neighbours w of v in Graph G
           if w is not visited 
                Q.enqueue( w ) //Stores w in Q to further visit its neighbours                       

      mark w as visited.

很明显，它没有指定你将顶点的邻居排列的顺序。

因此，如果您按顺序访问E的邻居：B，C，那么显然由于Queue数据结构的FIFO属性，节点B将在C之前被解除（从队列中取出）并且您将具有边缘B-F 。如果订单是C，B，那么由于类似的原因，边缘将是C-F。

一旦你理解了伪代码，你就会非常清楚地理解它。