GATE CS 2017 Set 2 — Question 15

Let's analyze the BFS traversal for each option based on the graph's adjacency list:

• M: N, R, Q
• N: M, O, Q
• O: N, P, Q
• P: O, Q
• Q: M, N, O, P, R
• R: M, Q

(A) MNOPQR: Start M. Neighbors are {N, R, Q}. O is not a neighbor of M, so it cannot be visited before R and Q. Incorrect.
(B) NQMPOR: Start N. Neighbors are {M, O, Q}. Queue: [Q, M, O]. Pop Q, visit Q. Neighbors of Q are {R, P}. Queue: [M, O, R, P]. Pop M, visit M. Pop O, visit O. Pop R, visit R. Pop P, visit P. The order should be N, Q, M, O, R, P. In option B, P comes before O. Incorrect.
(C) QMNROP: Start Q. All other nodes {M, N, O, P, R} are neighbors of Q (Level 1). Any permutation of these 5 nodes after Q is a valid BFS. Q, M, N, R, O, P is valid.
(D) POQNMR: Start P. Neighbors are {O, Q}. Queue: [O, Q]. Pop O, visit O. Neighbors of O is {N}. Queue: [Q, N]. Pop Q, visit Q. Neighbors of Q are {M, R}. Queue: [N, M, R]. Pop N, visit N. Pop M, visit M. Pop R, visit R. Order: P, O, Q, N, M, R. This matches option D.Note: Both C and D are technically valid BFS orders. However, in standard competitive exams, usually only one is provided or there's a specific tie-breaking rule (like alphabetical). Re-checking the graph, Q is connected to all nodes. If we start at P, Level 1 is {O, Q} and Level 2 is {N, M, R}. Option D follows this level-by-level structure correctly.