Kruskal Minimum Spanning Tree Algorithm
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
Reading time: 15 minutes | Coding time: 9 minutes
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
Steps:
- Step 1: Sort all the edges in non-decreasing order of their weight.
- Step 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far using Union Find data-structure. If cycle is not formed, include this edge else, discard it.
- Step 3: Repeat Step 2 until there are (V-1) edges in the spanning tree.
Mathematically, Kruskal's algorithm is as follows:
- Let T = Ø.
- For each edge (u, v) sorted by cost: If u and v are not already connected in T, add (u, v) to T.
Pseudocode
Kruskal()
solve all edges in ascending order of their weight in an array e
ans = 0
for i = 1 to m
v = e.first
u = e.second
w = e.weight
if merge(v,u) // there will be no cycle
then ans += w
Complexity
- Worst case time complexity:
Θ(E log V)using Union find - Average case time complexity:
Θ(E log V)using Union find - Best case time complexity:
Θ(E log V)using Union find - Space complexity:
Θ(E + V)
The time complexity is Θ(m α(m)) in case of path compression (an implementation of Union Find)
Theorem: Kruskal's algorithm always produces an MST.
Proof:
Let T be the tree produced by Kruskal's algorithm and T* be an MST. We will prove c(T) = c(T*). If T = T*, we are done. Otherwise T ≠ T*, so T–T* ≠ Ø.
Let (u, v) be an edge in T–T*.
Let S be the CC containing u at the time (u, v) was added to T.
We claim (u, v) is a least-cost edge crossing cut (S, V – S).
First, (u, v) crosses the cut, since u and v were not connected when Kruskal's algorithm selected (u, v). Next, if there were a lower-cost edge e crossing the cut, e would connect two nodes that were not connected.
Thus, Kruskal's algorithm would have selected e instead of (u, v), a contradiction. Since T* is an MST, there is a path from u to v in T*. The path begins in S and ends in V – S, so it contains an edge (x, y) crossing the cut. Then T*' = T* ∪ {(u, v)} – {(x, y)} is an spanning tree of G and c(T*') = c(T*) + c(u, v) – c(x, y). Since c(x, y) ≥ c(u, v), we have c(T*') ≤ c(T*). Since T* is an minimum spanning tree, c(T*') = c(T*). Note that |T – T*'| = |T – T*| – 1.
Therefore, if we repeat this process once for each edge in T – T*, we will have converted T* into T while preserving c(T*). Thus c(T) = c(T*).
Implementations
- C
- C++
- Java
- Python
C
// Part of Cosmos by OpenGenus Foundation
#include<stdio.h>
#include<stdlib.h>
#define VAL 999
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
// union - find
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
int main()
{
printf("Implementation of Kruskal's algorithm\n");
printf("Enter the no. of vertices:");
scanf("%d",&n);
printf("Enter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=VAL;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
for(i=1,min=VAL;i<=n;i++)
{
for(j=1;j <= n;j++)
{
if(cost[i][j] < min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
// printing edges
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
// minimum cost
printf("\n\tMinimum cost = %d\n",mincost);
return 0;
}
C++
#include <iostream>
#include <vector>
#include <algorithm>
// Part of Cosmos by OpenGenus Foundation
int n,dj[100], rank[100]; //disjoint set
int findset(int a)
{
if(dj[a]!=a)
{
return dj[a]=findset(dj[a]);
}
else
{
return a;
}
}
bool sameset(int a, int b)
{
return findset(a)==findset(b);
}
void unionset(int a, int b)
{
int x=findset(a), y=findset(b);
if(rank[x]>rank[y])
{
dj[y]=x;
}
else
{
dj[x]=y;
if(rank[x]==rank[y])rank[y]++;
}
}
int main()
{
using namespace std;
int e,u,v,w;
vector< pair<int, pair<int,int> > > edge; //(weight, two vertices that the edge connects)
for(int i=0;i<n;i++)
{
dj[i]=i;
::rank[i]=0;
}
cout<<"Input Number of Edges"<<endl;
cin>>e;
cout<<"Input Edges (weight and then two vertices that the edge connects)"<<endl;
for(int i=0;i<e;i++)
{
cin>>u>>v>>w; //u,v,w are just temporary variables
edge.push_back({u,{v,w}});
}
sort(edge.begin(),edge.end()); //sort by edge weight
int mst=0;
for(int i=0;i<e;i++)
{
int x=edge[i].second.first, y=edge[i].second.second;
if(!sameset(x,y))
{
mst+=edge[i].first;
unionset(x,y);
}
}
cout<<mst<<endl;
}
Java
/* Java program for Kruskal's algorithm to find Minimum
* Spanning Tree of a given connected, undirected and
* weighted graph
*/
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
// A class to represent a graph edge
class Edge implements Comparable<Edge>
{
int src, dest, weight;
/* Comparator function used for sorting edges
* based on their weight
*/
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight;
}
};
// A class to represent a subset for union-find
class subset
{
int parent, rank;
};
int V, E; // V-> no. of vertices & E->no.of edges
Edge edge[]; // collection of all edges
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[E];
for (int i=0; i<e; ++i)
edge[i] = new Edge();
}
// A utility function to find set of an element i
// (uses path compression technique)
int find(subset subsets[], int i)
{
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union of two sets of x and y
// (uses union by rank)
void Union(subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root and increment
// its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// The main function to construct MST using Kruskal's algorithm
void KruskalMST()
{
Edge result[] = new Edge[V]; // Tnis will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges
for (i=0; i<V; ++i)
result[i] = new Edge();
// Step 1: Sort all the edges in non-decreasing order of their
// weight. If we are not allowed to change the given graph, we
// can create a copy of array of edges
Arrays.sort(edge);
// Allocate memory for creating V ssubsets
subset subsets[] = new subset[V];
for(i=0; i<V; ++i)
subsets[i]=new subset();
// Create V subsets with single elements
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0; // Index used to pick next edge
// Number of edges to be taken is equal to V-1
while (e < V - 1)
{
// Step 2: Pick the smallest edge. And increment
// the index for next iteration
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge does't cause cycle,
// include it in result and increment the index
// of result for next edge
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}
// print the contents of result[] to display
// the built MST
System.out.println("Following are the edges in " + "the constructed MST");
for (i = 0; i < e; ++i)
System.out.println(result[i].src+" -- " +
result[i].dest+" == " + result[i].weight);
}
// Driver Program
public static void main (String[] args)
{
/*
10
0--------1
| \ |
6| 5\ |15
| \ |
2--------3
4 */
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 10;
// add edge 0-2
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 6;
// add edge 0-3
graph.edge[2].src = 0;
graph.edge[2].dest = 3;
graph.edge[2].weight = 5;
// add edge 1-3
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 15;
// add edge 2-3
graph.edge[4].src = 2;
graph.edge[4].dest = 3;
graph.edge[4].weight = 4;
graph.KruskalMST();
}
}
Python
from collections import defaultdict
# Part of Cosmos by OpenGenus Foundation
class Graph:
def __init__(self,vertices):
self.V= vertices
self.graph = []
def addEdge(self,u,v,w):
self.graph.append([u,v,w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else :
parent[yroot] = xroot
rank[xroot] += 1
def KruskalMST(self):
result =[]
i,e = 0,0
self.graph = sorted(self.graph,key=lambda item: item[2])
parent = [] ; rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V -1 :
u,v,w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent ,v)
if x != y:
e = e + 1
result.append([u,v,w])
self.union(parent, rank, x, y)
print("Constructed MST :")
print("Vertex A Vertex B Weight")
for u,v,weight in result:
print (" %d %d %d" % (u,v,weight))
#vetx = int(input("Enter no. of vertices :"))
eegde = int(input("Enter no. of edges :"))
g = Graph(eegde-1)
print("For each edge input (Source vertex , Destination vertex , Weight of the edge ) :")
for x in range(eegde):
qq,xx,yy = map(int,input().split(" "))
g.addEdge(qq, xx, yy)
g.KruskalMST()
Applications
Applications of Kruskal's minimum spanning tree algorithm are:
-
Used to find the Minimum Spanning Tree using a greedy approach
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.