GATE CSE 2017 | Set 2 | Question: 15

Question

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

• A. $\text{MNOPQR}$
• B. $\text{NQMPOR}$
• C. $\text{QMNROP}$
• D. $\text{POQNMR}$

Comments

same question asked in 2008 https://gateoverflow.in/417/gate2008-19

conclusion: Do all the previous year question. (all means all even subjective also)

Answer 1

In BFS, starting from a node, we traverse all node adjacent to it at first then repeat same for next nodes.

Here, we can see that only option (D) is following BFS sequence properly.

• As per BFS, if we start from $M$ then $RQN$ $($immediate neighbors of $M)$ have to come after it in any order but in $A$ here, $O$ comes in between. So, it is not BFS.
• As per BFS, if we start from $N$ then $QMO$ has to come after it in any order but in $B$ here, $P$ comes. So, it is not BFS.
• As per BFS, if we start from $Q$ then $MNOP$ has to come after it in any order but in $C$ here, $R$ comes. So, it is not BFS.

But $D$ is following the sequences.

So, D is the correct answer.

Comments

actually i was confused between c and d luckily put d

Answer 2

ans is D.

Answer 3

(D)

We traverse and process the nodes of the graph one level at a time. All options except D have skipped levels.

Answer 4

It will be d)

Answer 5

The possible order of visiting the nodes in Breadth First Search Algorithm, implementing using Queue Data Structure is

(Do it by option Elimination)
(a) MNOPQR – MNO is not the proper order R must come in between.
(b) NQMPOR – QMP is not the order O is the child of N.
(C) QMNROP – M is not the child of Q, so QMN is false.
(D) POQNMR – P → OQ → NMR is the correct sequence. Hence Option (D).