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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 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:

- $MNOPQR$
- $NQMPOR$
- $QMNPRO$
- $QMNPOR$

+18 votes

Best answer

- 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.
- NQMPOR: This is also not BFS. P is traversed before O.
- QMNPRO: Correct.
- QMNPOR: Incorrect. Because R needs to be traversed before O.(Because M is ahead of N in queue).

**Answer :- C**

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

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,873 questions

47,534 answers

146,065 comments

62,300 users