BFSでアルファベット順に並べ替え

Question

アルファベット順のBFSとそれがないBFSを区別するのにトラブルがあります。

たとえば、このグラフ（Eから始まる）でスパニングツリーを見つけるには、次のように入力します。

Starting G

{E、B}と{E、C}を追加した後

T after added EB and EC

Iは追加続行するかどうかわからない{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. 

その明確なそれはあなたが頂点の隣人をenqueする順番がどうあるべきかを指定していないこと。だから、

あなたが順番にEの隣人を訪問する場合：B、Cは、その後、明確に起因するキューのデータ構造のFIFOプロパティに、ノードBはdequedされます（から取り出しキュー）のCの前に、あなたはエッジB - Fを持っています。注文がC,Bである場合、同様の理由により、エッジはC-Fとなる。

擬似コードを理解すれば、それを非常にはっきりと理解できます。