edited by
35,330 views
31 votes
31 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}$
edited by

6 Answers

Best answer
36 votes
36 votes
  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
8 votes
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.
Answer:

Related questions

63 votes
63 votes
11 answers
1
Kathleen asked Sep 12, 2014
27,250 views
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance toonly vertex $a$only vertices $...
28 votes
28 votes
6 answers
2
Kathleen asked Sep 11, 2014
13,235 views
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity$\Theta(n)$$\Theta(m)$...
49 votes
49 votes
8 answers
3