Kruskal Minimum Spanning Tree Algorithm

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Algorithm
Complexity
Pseudocode
Implementations
Applications
Discussions

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.

kruskal

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
See Applications of Minimum Spanning Tree

Graph Algorithms Minimum Spanning Tree (MST) Greedy Algorithms kruskal minimum spanning tree