Past exam question: 2078 Baishakh (Back), Q11
Open in the Padhaiko appDefine minimum spanning tree with suitable example. Show step by step solution to find the minimum spanning tree of the graph below using Prim's algorithm.
[figure: undirected weighted graph on vertices A, B, C, D, E, F with edges A-B(7), A-C(6), A-D(1), B-C(8), C-D(5), C-E(3), D-E(4), D-F(5), E-F(2)]
Solution
Definition and Example of Minimum Spanning Tree (MST): Given a connected, undirected, weighted graph , a Minimum Spanning Tree (MST) is an acyclic connected subgraph containing all vertices with edges such that the sum of edge weights is minimized.
- Example: In a 3-node triangle
X-Y(2), Y-Z(3), X-Z(10), removingX-Z(10)leaves the MST{X-Y, Y-Z}with total weight .
Prim's Algorithm Trace (Starting from Vertex A): Maintain visited set and grow the tree by repeatedly picking the minimum-weight edge crossing :
- Initial: . Candidate edges:
A-D(1),A-C(6),A-B(7).- Pick
A-D(1). .
- Pick
- From : Candidates:
D-E(4),C-D(5),D-F(5),A-C(6),A-B(7).- Pick
D-E(4). .
- Pick
- From : Candidates:
E-F(2),C-E(3),C-D(5),D-F(5),A-C(6),A-B(7).- Pick
E-F(2). .
- Pick
- From : Candidates:
C-E(3),C-D(5),A-C(6),A-B(7).- Pick
C-E(3). .
- Pick
- From : Candidates crossing to
B:A-B(7),B-C(8).- Pick
A-B(7). (all 6 vertices covered!).
- Pick
MST Verification: Selected edges (): A-D(1), D-E(4), E-F(2), C-E(3), A-B(7). Total MST weight = .
- Selected MST Edges (Prim's from
A):A-D(1),D-E(4),E-F(2),C-E(3),A-B(7). - Minimum Total Weight: .