BFS 中的字母顺序

Question

我很难区分按字母顺序排列的 BFS 和不按字母顺序排列的 BFS。

例如求这张图中的生成树（从E开始）

Starting G

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

T after added EB and EC

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

Answer 1

I'm not sure whether to continue adding {B,F} or {C,F}. Thank you very much.

好吧，答案取决于您在 [=12= 的队列中添加顶点 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 .

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

BFS 中的字母顺序

Alphabetical ordering in BFS

breadth-first-search

alphabetical