in Algorithms edited by
16,585 views
23 votes

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is:

  1. $\text{MNOPQR}$
  2. $\text{NQMPOR}$
  3. $\text{QMNPRO}$
  4. $\text{QMNPOR}$
in Algorithms edited by
16.6k views

1 comment

Similar question :-

Gate 2017

0

5 Answers

28 votes
 
Best answer
  1. $\text{MNOPQR}:$ If you try to run BFS, after $\text{M},$ you must traverse $\text{NQR}$ (In some order). Here, $\text{P}$ is traversed before $\text{Q},$ which is wrong.
  2. $\text{NQMPOR:}$ This is also not BFS. $\text{P}$ is traversed before $\text{O.}$
  3. $\text{QMNPRO:}$ Correct.
  4. $\text{QMNPOR:}$ Incorrect. Because $\text{R}$ needs to be traversed before $\text{O}.$ (Because $\text{M}$ is ahead of $\text{N}$ in queue).

Answer:  C

edited by

2 Comments

Option (c)   ------- QMNPRO    is correct.....what does it convey .....If it conveys " the shortest path from Q to every vertex in graph ", then how can we explain it ???
0
Why option D not correct?

when we start BFS on Q vertex we get three nodes {M, N , P}  TO INSERT in QUEUE but these nodes can be any order because representation is not defined that why option D might be correct.
0
8 votes
Ans- C

Option (A) is MNOPQR. It cannot be a BFS as the traversal starts with M, but O is visited before N and Q. In BFS all adjacent must be visited before adjacent of adjacent. Option (B) is NQMPOR. It also cannot be BFS, because here, P is visited before O. (C) and (D) match up to QMNP. We see that M was added to the queue before N and P (because M comes before NP in QMNP). Because R is M's neighbor, it gets added to the queue before the neighbor of N and P (which is O). Thus, R is visited before O.
0 votes
In BFS using Queue data structure the correct option is C.
0 votes
In this Question take options one – by – one, it become too easy to solve :)
0 votes
Answer:

Related questions