A weighted undirected graph has edges A–B (1), B–C (2), A–C (3), B–D (4), C–D (5), C–E (6) and D–E (7). What is the total weight of its minimum spanning tree found by Kruskal’s algorithm?
Correct answer B. 13
Explanation
Kruskal's algorithm takes edges in increasing weight order and keeps each one that does not form a cycle. It accepts A–B (1) and B–C (2), rejects A–C (3) because A and C are already connected, accepts B–D (4), rejects C–D (5), then accepts C–E (6). Four edges join five vertices, and 1 + 2 + 4 + 6 = 13.
Answer checked How we write and check questions
Discussion