Project ForgeThe 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?
Edges: M-N, M-Q, M-R, N-O, N-Q, O-Q, O-P, Q-P
- AMNOPQR
- BNQMPOR
- CQMNROP
- POQNMR
Explanation
Starting BFS from P: visit P first, then P's neighbors O and Q (in the order POQ). Then from O and Q's unvisited neighbors: N and M remain. N is adjacent to both O and Q (already visited), and M is adjacent to N, Q. Processing O's queue entry reveals N, then Q's entry reveals M (already-queued N is skipped) — giving the order P,O,Q,N,M,R, i.e. POQNMR, which is a valid BFS order (each newly visited node is reachable from an already-visited node already in the queue, and the order respects level-by-level expansion).
Source: GATE CS 2017 (Session 2) (2017)
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.