Register

GATE CSE 2008 | Question: 19

• edited by
36,329 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
User Avatar

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
User Avatar
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.
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

8.3k
views
3 answers
23 votes
Ishrat Jahan asked Oct 28, 2014
8,316 views
GATE IT 2008 | Question: 47
Consider the following sequence of nodes for the undirected graph given below:$a$ $b$ $e$ $f$ $d$ $g$ $c$a$ $b$ $e$ $f$ $c$ $g$ $d$a$ $d$ $g$ $e$ $b$ $c$ $f$a$ $ ... (s)?$1$ and $3$ only$2$ and $3$ only$2, 3$ and $4$ only$1, 2$ and $3$ only
User Avatar
19.0k
views
4 answers
64 votes
Daggerhunt asked Nov 16, 2014
18,960 views
GATE CSE 2000 | Question: 2.19
Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ ... not an edge in $G$ then $u$ and $v$ must have the same parent in $T$
User Avatar
28.3k
views
11 answers
63 votes
Kathleen asked Sep 12, 2014
28,346 views
GATE CSE 2008 | Question: 45
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 $a, e, f, g, h$only vertices $a, b, c, d$all the vertices
User Avatar
14.0k
views
6 answers
28 votes
Kathleen asked Sep 11, 2014
13,983 views
GATE CSE 2008 | Question: 7
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)$\Theta(m+n)$\Theta(mn)$
User Avatar
Link Copied!