Use Kruskal’s Algorithm to find the minimum spanning tree for the weighted graph. Give the total weight of the minimum spanning tree.
Solution:-
Step 1. Find the edge with the smallest weight.
Select edge AB (weight: 72)
Step. Find the next-smallest edge in the graph.
Select edge CD (weight : 77).
Step 3. Find the next-smallest edge in the graph that does not create a circuit.
Select edge AC (weight: 81).
There three edges create a subgraph that contains all of the graph’s four vertices, is connected, and contains no circuits. Furthermore, since the edges with the smallest weights were chosen, the resulting spanning tree should be the minimum spanning tree for the weighted graph.
The following tree matches the shape of the minimum spanning tree.
From the figure, we see that the total weight of the minimum spanning tree is
72 + 77 +81 = 230