Question

The weights of edges in a graph are shown in the table above. Find the minimum cost spanning tree on the graph above using Kruskal's algorithm. What is the total cost of the tree?

Answer 1

Kruskal Algorithm

This algorithm first sorts all the edges according to weight in non-decreasing order.

Then it picks edge one by one based on sorted order. If adding edge to tree creates cycle discard it otherwise add it.

Total vertices in Graph = 6

Number of edges in Minimum Spanning tree = Number of vertices - 1 = 5

Weight of Edged between two vertices from the matrix

A and B = 39

A and C = 8

A and D = 40

A and E = 15

A and F = 20

B and C = 1

B and D = 23

B and E = 9

B and F = 7

C and D = 28

C and E = 35

C and F = 42

D and E = 38

D and F = 31

E and F = 25

Let's sort the edges based on their weight in non-decreasing order.

Weight	Source	Destination
1	B	C
7	B	F
8	A	C
9	B	E
15	A	E
20	A	F
23	B	D
25	E	F
28	C	D
31	D	F
35	C	E
38	D	E
39	A	B
40	A	D
42	C	F

Now, Pick edges one by one from sorted list

Pick entry B-C. There is no cycle formed. We will include this edge.

Pick entry B-F. There is no cycle formed. We will include this edge

Pick entry A-C. There is no cycle formed. We will include this edge

Pick entry B-E. There is no cycle formed. We will include this edge

Pick entry A-E. This will form cycle. We will not include this edge.

Pick entry A-F. This will form cycle. We will not include this edge.

Pick entry B-D. There is no cycle formed. We will include this edge

All vertices are connected now so we have got minimum spanning tree with weight = 1+7+8+9+23 = 48