The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.2k 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 (68.8k points)
recategorized by | 1.2k views

3 Answers

+15 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 need to be traversed before O.(Because M is ahead of N in queue).

Answer :- > C

answered by Veteran (48.6k points)
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.
+5 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 Loyal (4.9k points)
–1 vote
In BFS using Queue data structure the correct option is C.
answered by Veteran (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

32,620 questions
39,267 answers
109,737 comments
36,655 users