edited by
7,929 views
29 votes
29 votes

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?

  1. $\text{MNOPQR}$
  2. $\text{NQMPOR}$
  3. $\text{QMNROP}$
  4. $\text{POQNMR}$
edited by

5 Answers

Best answer
21 votes
21 votes

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.

edited by
1 votes
1 votes
(D)

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

Related questions

49 votes
49 votes
8 answers
1