The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.4k views

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. $MNOPQR$
  2. $NQMPOR$
  3. $QMNPRO$
  4. $QMNPOR$
asked in Algorithms by Veteran (59.4k points)
edited by | 1.4k views

3 Answers

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

Answer :-  C

answered by Boss (42.5k points)
edited ago by
0
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.
+6 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.
answered by Active (4.7k points)
0 votes
In BFS using Queue data structure the correct option is C.
answered by Boss (19.6k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,204 questions
43,662 answers
124,117 comments
42,948 users