DSA - Graphs and Hashing -Q12

Question

Consider the following graph. If there is ever a decision between multiple neighbor nodes in the BFS or DFS algorithms, assume we always choose the letter closest to the beginning of the alphabet first. In what order will the nodes be visited using a Breadth First Search and Depth First Search respectively ?

 

                         

(A) BFS : ABDCEGHF  

      DFS: ABGFEHCG

(B) BFS : ABDECGHF  

      DFS: ABCEHFGD

(C)  BFS : ABDCEGFH  

       DFS: ABCEHFGD

(D)  BFS : ABDCEGHF  

       DFS: ABCEHFGD

Answer 1

From the options we know that we need to start at vertex A.

It is given that "If there is ever a decision between multiple neighbor nodes in the BFS or DFS algorithms, assume we always choose the letter closest to the beginning of the alphabet first."

BFS : 

After A, we will visit its neighbours B,D, in that order. Now, we will visit B's neighbours C,E,G in that order. Then D's neighbours are already visited. Then C's neighbours are already visited. Then E's neighbours i.e. H is visited. Then G's neighbours i.e. F is visited.

So, BFS = ABDCEGHF 

---

DFS : First visit A, then visit B. Then visit C. Then visit E. Then visit H. Then visit F. Then visit G. Then visit D.

DFS: ABCEHFGD