GATE CS 2017 Set 2 Q15 — Graph Traversals (BFS, DFS)

In a Breadth-First Search (BFS) traversal, vertices must be visited level-by-level in increasing order of their shortest path distance from the starting vertex. That is, all vertices at distance $d$ from the start vertex must be visited before any vertex at distance $d+1$ is visited.

Let us analyze the graph's structure and the options:

• Option D ($ext{POQNMR}$): If we start the BFS at vertex $\text{P}$:
  • Level 0 (distance 0): $\text{P}$
  • Level 1 (distance 1): $\text{O, Q}$
  • Level 2 (distance 2): $\text{N, M}$
  • Level 3 (distance 3): $\text{R}$
  Since the sequence $\text{P} \to \text{O} \to \text{Q} \to \text{N} \to \text{M} \to \text{R}$ strictly visits vertices level-by-level, it is a valid BFS traversal.
• Other Options: In options A, B, and C, a vertex at a greater distance is visited before all vertices at a closer distance are exhausted, which violates the BFS property. For example, in Option A ($\text{MNOPQR}$), starting at $\text{M}$, the vertex $\text{N}$ (at distance 2) is visited before $\text{O}$ and $\text{R}$ (at distance 1).