Alphabetical ordering in BFS

Question

I have troubles differentiating between BFS with alphabetical ordering and BFS without it.

For example, to find a spanning tree in this graph (starting from E).

Starting G

After adding {E,B} and {E,C}

T after added EB and EC

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

Answer 1

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

Well, the answer depends on the order in which you add the vertices B and C in your queue of BFS algorithm. If you look at the algorithm:

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.

Its clear that it does not specify what should be the order in which you enque the neighbours of a vertex.

So if you visit the neighbours of E in the order: B , C , then clearly due to FIFO property of Queue data structure, node B will be dequed(taken out of queue) before C and you will have the edge B--F. If the order is C , B, then the edge would be C--F for similar reasons.

Once you understand the pseudocode, you will understand it very clearly.