Draw the minimum cost spanning tree using Kruskals algorithm. Also find its cost with all intermediate steps
1 Answer

enter image description here

A minimum spanning tree can be defined as a spanning tree with weight less than or equal to the weight of every other spanning tree.

Let us find the minimum spanning tree for the given graph.

Step 1: Remove all loops

Here as no loops are present, we skip this step.

Step 2: Remove all Parallel edges(i.e edges having multiple values)

If so eliminate the edge with highest value and keep the one with least value intact. Here since such edges are not present, we skip this step.

Step 3: Sort the edges according to minimum weights.

Edge Value
A-D 1
E-F 2
C-E 3
E-D 4
C-D 5
D-F 5
A-C 6
A-B 7
C-B 8

Step 4: Construct minimum spanning tree.

Here we go from top to bottom of the above table by joining the given edges. An edge is discarded is it results in a cycle formation.

enter image description here

Please log in to add an answer.