Register

GATE CSE 2008 | Question: 19

• edited by
44,621 views
47 47 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}$

6 Answers

Best answer
52 52 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
10 10 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.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2008 | Ques...Next → · GATE CSE 2008 | Ques...
← Previous in category · GATE CSE 2008 | Ques...Next in category → · GATE CSE 2008 | Ques...
Position:
Show:

Related questions

74 74 votes
4 answers 4 answers
35.7k
35.7k views
Kathleen asked Sep 12, 2014
35,724 views
GATE CSE 2008 | Question: 36
Which of the following are NOT true in a pipelined processor?Bypassing can handle all RAW hazardsRegister renaming can eliminate all register carried WAR hazardsControl h...
32 32 votes
4 answers 4 answers
12.7k
12.7k views
Ishrat Jahan asked Oct 28, 2014
12,717 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$ $d$ $b$...
108 108 votes
7 answers 7 answers
29.3k
29.3k views
Daggerhunt asked Nov 16, 2014
29,271 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$ be t...
84 84 votes
12 answers 12 answers
49.7k
49.7k views
Kathleen asked Sep 12, 2014
49,738 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 $...