PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q11

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Graphs

Question

Explain the concept of minimum spanning tree (MST) and find MST for the following graph using Kruskal's algorithm:

[figure: undirected weighted graph on 9 vertices A, B, C, D, E, F, G, H, I with edges A-B(4), A-H(7), B-C(18), B-H(11), C-D(7), C-I(2), D-E(9), D-F(14), E-F(10), F-G(2), G-H(1), G-I(6), H-I(7)]

Solution

Concept of Minimum Spanning Tree (MST): For a connected, undirected, weighted graph , a spanning tree is an acyclic connected subgraph that includes all vertices using exactly edges. A Minimum Spanning Tree (MST) is a spanning tree whose total edge weight is minimum among all possible spanning trees.

Kruskal's Algorithm — Sorted Edge List: With , the MST must contain edges. Sort all edges in non-decreasing order of weight and add each edge if it does not create a cycle:

EdgeWeightActionReason
G-H1AcceptConnects {G, H}
C-I2AcceptConnects {C, I}
F-G2AcceptConnects {F, G, H}
A-B4AcceptConnects {A, B}
G-I6AcceptMerges {F, G, H} and {C, I}
A-H7AcceptMerges {A, B} and {C, F, G, H, I}
C-D7AcceptConnects D
H-I7RejectH and I already connected (cycle H-G-I-H)
D-E9AcceptConnects E (8 edges reached — MST complete)

Remaining Edges & Total Cost Verification:

Answer:

All past exam questions for Data Structure and Algorithms