KRUSKAL’S ALGORITHM FOR FINDING MST

4 min readApr 10, 2022

And I’m here to discuss about my favourite algorithm for finding the Minimum Cost Spanning Tree.
And yes, you guessed it right.
In this blog, we will discuss about Kruskal’s Algorithm.
But before moving directly towards the Kruskal’s algorithm, we should first understand basic terms such as spanning tree and minimum spanning tree.

Spanning tree — A spanning tree is the subgraph of an undirected complete graph.

Here all the spanning trees which are possible for the given complete graph.

Minimum Spanning tree — Minimum spanning tree can be defined as the spanning tree in which the sum of the weights of the edge is minimum.
Here is an example of a minimum spanning tree.

Here the cost of the Minimum spanning tree is 7.

Now let’s move to our main topic
That is Kruskal’s Algorithm.
Kruskal’s algorithm uses the greedy approach for finding a minimum spanning tree.
Kruskal’s algorithm treats every node as an independent tree and connects one with another only if it has the lowest cost compared to all other options available.

Steps to Kruskal’s algorithm:

Sort the graph edges with respect to their weights.

Start adding edges to the minimum spanning tree from the edge with the smallest weight until the edge of the largest weight.

Only add edges which don’t form a cycle — edges which connect only disconnected components.

To understand Kruskal’s Algorithm more clearly, and in depth,
Let’s take an example.

Write down the weights of all the edges in the above graph

Now, sort the edges in the ascending order of their weights.

Now start Adding edges with least weight sequentially ;

We begin with the edges with least weight/cost.

Step -3

Now, Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Step-4
Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle

So, the final minimum spanning tree obtained from the given weighted graph by using Kruskal’s algorithm is

Minimum cost of the spanning tree:

The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Complexity of Kruskal’s Algorithm

Kruskal’s algorithm’s time complexity is O(E log V)

where :

E : no. of edges

V : no. of vertices\nodes

A program to implement kruskal’s algorithm in C++.

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];
void init()
{
for(int i = 0;i < MAX;++i)
id[i] = i;
}
int root(int x)
{
while(id[x] != x)
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}
void union1(int x, int y)
{
int p = root(x);
int q = root(y);
id[p] = id[q];
}
long long kruskal(pair<long long, pair<int, int> > p[])
{
int x, y;
long long cost, minimumCost = 0;
for(int i = 0;i < edges;++i)
{
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
if(root(x) != root(y))
{
minimumCost += cost;
union1(x, y);
}
}
return minimumCost;
}
int main()
{
int x, y;
long long weight, cost, minimumCost;
init();
cout <<”Enter Nodes and edges”;
cin >> nodes >> edges;
for(int i = 0;i < edges;++i)
{
cout<<”Enter the value of X, Y and edges”;
cin >> x >> y >> weight;
p[i] = make_pair(weight, make_pair(x, y));
}
sort(p, p + edges);
minimumCost = kruskal(p);
cout <<”Minimum cost is “<< minimumCost << endl;
return 0;
}

Applications of Minimum Spanning Tree Problem :

Network design.
– telephone, electrical, hydraulic, TV cable, computer, road

Approximation algorithms for NP-hard problems.
– traveling salesperson problem, Steiner tree

Indirect applications.
– max bottleneck paths
– LDPC codes for error correction
– image registration with Renyi entropy
– learning salient features for real-time face verification
– reducing data storage in sequencing amino acids in a protein
– model locality of particle interactions in turbulent fluid flows
– autoconfig protocol for Ethernet bridging to avoid cycles in a network.