Past exam question: 2074 Bhadra (Regular), Q10
Open in the Padhaiko appQuestion
Explain Depth first traversal in graph. Create minimum spanning tree for the following graph using Kruskal's algorithm.
[figure: undirected weighted graph on 7 vertices A, B, C, D, E, F, G with edges A-B(5), A-C(2), A-D(6), B-D(3), B-F(2), B-G(3), C-D(4), C-E(1), D-F(2), D-G(4), E-F(6), F-G(1)]
Solution
Depth-First Traversal (DFS) in a Graph: DFS starts at a source vertex, marks it visited, and recursively (or via a Stack) explores an unvisited adjacent neighbor as deeply as possible before backtracking to explore remaining unvisited neighbors. Time complexity is with an adjacency list.
Kruskal's Algorithm — Sorted Edges (, Target Edges):
| Edge | Weight | Action | Connected Components |
|---|---|---|---|
C-E | 1 | Accept | {C, E} |
F-G | 1 | Accept | {F, G} |
A-C | 2 | Accept | {A, C, E} |
B-F | 2 | Accept | {B, F, G} |
D-F | 2 | Accept | {B, D, F, G} |
B-D | 3 | Reject | Forms cycle B-F-D-B |
B-G | 3 | Reject | Forms cycle B-F-G-B |
C-D | 4 | Accept | {A, B, C, D, E, F, G} (6 edges — complete!) |
Total Minimum Weight:
Answer:
- DFS: Traverses deep along each branch via recursion or a stack before backtracking ().
- Kruskal's MST Edges:
C-E(1),F-G(1),A-C(2),B-F(2),D-F(2),C-D(4). - Total Minimum Weight: .