The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.3k 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)
recategorized by | 1.3k 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 need to be traversed before O.(Because M is ahead of N in queue).

Answer :- > C

answered by Boss (42.4k points)
edited 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.6k points)
0 votes
In BFS using Queue data structure the correct option is C.
answered by Boss (19.7k 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

34,770 questions
41,730 answers
118,876 comments
41,381 users