Past exam question: 2077 Chaitra (Regular), Q11
Open in the Padhaiko appQuestion
Define depth first and breadth first traversal. Construct the minimum spanning tree (MST) for the given graph using Krushkal's algorithm.
[figure: undirected weighted graph on 7 vertices 1, 2, 3, 4, 5, 6, 7 with edges 1-2(28), 1-6(10), 2-3(16), 2-7(14), 3-4(12), 4-5(22), 4-7(18), 5-6(25), 5-7(24)]
Solution
Depth-First and Breadth-First Graph Traversal:
- Depth-First Traversal (DFT / DFS): Uses a Stack (or recursion) to explore along one branch as deep as possible until reaching an unvisited dead end, then backtracks to explore remaining neighbors.
- Breadth-First Traversal (BFT / BFS): Uses a Queue to visit all immediate neighbors at distance 1 before advancing to distance 2, 3, and so on in level order.
Kruskal's Algorithm — Sorted Edges (, Target Edges):
| Edge | Weight | Action | Connected Components |
|---|---|---|---|
1-6 | 10 | Accept | {1, 6} |
3-4 | 12 | Accept | {3, 4} |
2-7 | 14 | Accept | {2, 7} |
2-3 | 16 | Accept | {2, 3, 4, 7} |
4-7 | 18 | Reject | 4 and 7 already connected (4-3-2-7) |
4-5 | 22 | Accept | {2, 3, 4, 5, 7} |
5-7 | 24 | Reject | 5 and 7 already connected (5-4-3-2-7) |
5-6 | 25 | Accept | {1, 2, 3, 4, 5, 6, 7} (6 edges — complete!) |
Remaining Edge and Total Weight:
1-2(28)is skipped since all 7 vertices are connected.- Total Minimum Weight:
Answer:
- DFT/BFT: DFS explores deep via a stack/recursion; BFS explores level-by-level via a queue.
- Kruskal's MST Edges:
1-6(10),3-4(12),2-7(14),2-3(16),4-5(22),5-6(25). - Total Minimum Weight: .