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?

Breadth First Search (BFS) visits all vertices at distance $k$ before visiting any vertex at distance $k+1$ from the source vertex.

Let us evaluate the options:

• (A) MNOPQR: Starts at $M$. Distance-1 neighbors of $M$ are $\{N, R, Q\}$. However, $O$ (which is at distance $2$) is visited before $R$ and $Q$. Hence, invalid.

• (B) NQMPOR: Starts at $N$. Distance-1 neighbors of $N$ are $\{M, O, Q\}$. Here, $P$ (at distance $2$) is visited before $O$ (at distance $1$). Hence, invalid.

• (C) QMNROP: Starts at $Q$. Distance-1 neighbors of $Q$ are $\{M, N, O, P\}$. Here, $R$ (at distance $2$) is visited before $O$ and $P$ (at distance $1$). Hence, invalid.

• (D) POQNMR: Starts at $P$.

  1. Enqueue $P$. Level $0$: $P$.

  2. Dequeue $P$, enqueue unvisited neighbors: $O, Q$. Queue: $[O, Q]$. Level $1$: $\{O, Q\}$.

  3. Dequeue $O$, enqueue unvisited neighbor: $N$. Queue: $[Q, N]$.

  4. Dequeue $Q$, enqueue unvisited neighbor: $M$. Queue: $[N, M]$.

  5. Dequeue $N$, no unvisited neighbors. Queue: $[M]$.

  6. Dequeue $M$, enqueue unvisited neighbor: $R$. Queue: $[R]$.

  7. Dequeue $R$.

  The sequence of visited nodes is P $\to$ O $\to$ Q $\to$ N $\to$ M $\to$ R, which is valid.

Therefore, option (D) is correct.