Project ForgeConsider a graph with nodes M, N, O (top row) and R, Q, P (bottom row), with edges M-R, M-Q, N-Q, N-O, O-P, Q-P. The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of this graph is
- AMNOPQR
- BNQMPOR
- QMNPRO
- DQMNPOR
Explanation
Starting BFS from Q (neighbors M, N, P, in that order): visit Q, enqueue M,N,P. Dequeue M (visit, 2nd) — its unvisited neighbor R gets enqueued. Dequeue N (visit, 3rd) — its unvisited neighbor O gets enqueued. Dequeue P (visit, 4th) — no new neighbors (O,Q both already visited/queued). Dequeue R (visit, 5th). Dequeue O (visit, 6th). This gives exactly Q,M,N,P,R,O — matching option (C).
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.