PrepSnap logoPrepSnap
Pass

Question

1.
2.
3.
4.
Answer (Detailed Solution Below)

Option 2 : 1, 2, 3, 4, 5, 6 / 1, 2, 3, 4, 5, 6

Advertisement

Detailed Solution

सही उत्तर 1, 2, 3, 4, 5, 6 / 1, 2, 3, 4, 5, 6 है।

Key Points
Helpful?
PrepSnapprepsnap.in • Part -A

Question:

An undirected graph has vertices 1 to 6 with adjacency lists (neighbours in ascending order): 1: 2, 3; 2: 1, 4, 5; 3: 1, 6; 4: 2; 5: 2, 6; 6: 3, 5. The BFS traversal order starting from vertex 1 (neighbours enqueued in ascending order) is— / अदिष्ट ग्राफ़ के शीर्ष 1 से 6 हैं, संलग्नता सूचियाँ (आरोही क्रम में पड़ोसी): 1: 2, 3; 2: 1, 4, 5; 3: 1, 6; 4: 2; 5: 2, 6; 6: 3, 5। शीर्ष 1 से आरंभ BFS भ्रमण क्रम (पड़ोसी आरोही क्रम में कतारबद्ध) है—

1.
1, 2, 4, 5, 3, 6 / 1, 2, 4, 5, 3, 6
2.
1, 2, 3, 4, 5, 6 / 1, 2, 3, 4, 5, 6
3.
1, 3, 2, 6, 5, 4 / 1, 3, 2, 6, 5, 4
4.
1, 2, 3, 6, 4, 5 / 1, 2, 3, 6, 4, 5

Correct Answer: 1, 2, 3, 4, 5, 6 / 1, 2, 3, 4, 5, 6

BFS visits level by level: 1, then 2, 3, then 4, 5 (from 2) and 6 (from 3) — order 1, 2, 3, 4, 5, 6. Option (a) is the DFS-like trap that dives to 4 before finishing level 1. / BFS स्तर-दर-स्तर जाता है: 1, फिर 2, 3, फिर 4, 5 (2 से) व 6 (3 से) — क्रम 1, 2, 3, 4, 5, 6। विकल्प (a) DFS-जैसा जाल है जो स्तर 1 पूर्ण किए बिना 4 में उतरता है।

Downloaded from PrepSnap (prepsnap.in)