Minimal Spanning Trees and Kruskal’s Algorithm

Given a weighted graph G, it is often desired to generate a spanning tree such that the sum of the weights of the tree edges is a minimum. Such a tree is called a Minimum Spanning Tree. Such a method is the cheapest way of connecting all nodes of G.

Kurskal’s Algorithm

Kurskal’s algorithm is a method to create Minimum Cost Spanning Trees from a given network. The min cost S.T is built edge by edge by selecting those edges first which have least cost(weight). Each edge is included only once. If there are n nodes in the network, there will be exactly (n-1) edges in the Minimum Cost Spanning Tree.

Consider the graph below –


Applying Kurskal’s Algorithm, the resulting Minimum Cost Spanning Tree is as shown below –