GATE CS 2008 Q19 — Graph Traversals (BFS, DFS)

Based on the graph structure, the connections between the vertices are as follows:

• $Q$ is connected to $M$ and $N$.
• $M$ is connected to $P$ and $R$.
• $N$ is connected to $P$ and $O$.
• $O$ is connected to $R$.

Let us trace the Breadth First Search (BFS) traversal starting from vertex $Q$ using a FIFO queue:

1. Start at $Q$: Visit $Q$. Queue = $[Q]$.
2. Dequeue $Q$: Visit its neighbors $M$ and $N$. Queue = $[M, N]$.
3. Dequeue $M$: Visit its unvisited neighbors $P$ and $R$. Queue = $[N, P, R]$.
4. Dequeue $N$: Visit its unvisited neighbor $O$. Queue = $[P, R, O]$.
5. Dequeue remaining: Dequeue and visit $P$, then $R$, and finally $O$.

This sequence yields the traversal order $\text{QMNPRO}$.

Why Option D ($\text{QMNPOR}$) is incorrect:
Because $M$ is dequeued before $N$, the neighbor of $M$ (which is $R$) is enqueued before the neighbor of $N$ (which is $O$). Due to the FIFO property of the queue, $R$ must be dequeued and visited before $O$. Therefore, $\text{QMNPRO}$ is a valid BFS order, but $\text{QMNPOR}$ is not.