in Algorithms edited by
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

1 comment

Similar question :-

Gate 2017


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


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 ???
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.
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

Related questions