Kruskal’s Algorithm

Kruskal's algorithm is a greedy algorithm in graph theory that is used to find the Minimum spanning tree (A subgraph of a graph $G(V,E)$ which is a tree and includes all the vertices of the given graph such that the sum of the weight of the edges is minimum) of a given connected, weighted, undirected graph.

In case, the graph is not connected, on applying Kruskal's algorithm we can find the MST of each connected component.

Takeaways

Complexities of the Kruskal's Algorithm

• Time Complexity :$O(E*log(E))$
• Space Complexity:$O(E)$

Introduction to Kruskal’s Algorithm

Suppose that there are some villages in a town, you being the Mayor of the town want to visit all the villages but you have very little time for it.

So you will be interested in visiting the villages in such a way that the total distance covered by you during the visit is minimum possible. Isn’t it.?

If you try to formulate the above problem in terms of graph theory, by considering villages as the vertices, roads connecting them as the edges, and the distance of each road as the weight of the corresponding edge.

Kurskal's algorithm will help you in this case because it is used to find the minimum spanning tree (MST) of any given connected, weighted, undirected graph. Before discussing any further details of Kruskal’s algorithm let’s see what is meant by a Minimum spanning tree of a graph.

A spanning tree is a subgraph of a connected, undirected graph such that it is a tree and it includes all the vertices. So a minimum spanning tree would correspond to a spanning tree with the minimum weight. Where the weight of a spanning tree is the sum of the weight of the edges present in it.

For Example:

The below-given image shows a graph $G$ with 6 vertices and 9 edges

This graph can have multiple spanning tree some of which are shown below with their respective weights.

But they can not be considered as minimum spanning trees as there exists at least one spanning tree with an even smaller sum of edge weights.The MST of the graph is –

The MST of the given graph has a weight of 17, which means that we can’t form any other spanning tree of graph $G$ whose weight is less than 17.

Kruskal’s Algorithm Implementation

The main idea of Kruskal's algorithm to find the MST of a graph $G$ with $V$ vertices and $E$ edges is

• to sort all the edges in ascending order according to their weights.
• Then select the first $V-1$ edges such that they do not form any cycle within them.
  
• One thing that can be observed here is, that for any graph with $V$ vertices, we are interested in including only $V-1$ edges as part of the MST. It is because we need only that many edges to include all the vertices.

Let us understand how Kruskal’s Algorithm works by the following algorithm and example

Algorithm of Kruskal’s

For any graph, $G=(V,E)$, finding an MST using Kruskal’s algorithm involves the following steps –

• Sort all the edges of the graph in ascending order of their weights.
• Check the edge with minimum weight, if including it in the answer forms a cycle discard it, otherwise include it in the answer.
• Repeat the above step until we have chosen $V-1$ edges.

Example of Kruskal’s Algorithm

Let’s say we want to find the MST of the underlying connected, weighted, undirected graph with $6$ vertices and $9$ edges-

Now as per the algorithm discussed above, to find the MST of this graph –

1. We will write all the edges sorted in ascending order according to their respective weights
2. Then we will select the first $V-1=5$ edges which do not form cycles.

• Step 1 –
  Sort the edges in ascending order. Here is the list after sorting. No. $u$ $v$ Weight 1 4 5 2 2 4 6 2 3 3 4 3 4 2 3 3 5 3 5 4 6 5 6 5 7 2 5 6 8 1 2 7 9 1 3 8
• Step 2 –
  Choose 5 edges from starting which do not form a cycle.
  • Checking edge $4\Longleftrightarrow 5$ –
    This is the first edge so it can’t form any cycle hence including this in result –

• Checking for edge $3\Longleftrightarrow 4$ –
  Including this edge in the result does not form any cycle.
  

• Checking for edge $2\Longleftrightarrow 3$ –
  Again including this edge in the result does not form any cycle.

• Checking for edge $3\Longleftrightarrow 5$ –
  Including this edge in the result forms a cycle $3 \rightarrow 4 \rightarrow 5 \rightarrow 3$, hence not including this in the result.
  

• Checking for edge $5\Longleftrightarrow 6$ –
  Including this edge in the result forms a cycle $4 \rightarrow 5 \rightarrow 6 \rightarrow 4$, hence not including this in the result.
  

• Checking for edge $2\Longleftrightarrow 5$ –
  Including this edge in the result forms a cycle $2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$, hence not including this in the result.

• Checking for edge $1\Longleftrightarrow 2$ –
  Including this edge in the result does not form any cycle. By including this, we have included 5 edges so now the result will correspond to the minimum spanning tree.

After including all $5$ edges, the MST will look like this –

So the weight of MST can be calculated as $7+3+3+2+2=17$.

Pseudocode of Kruskals Algorithm

MST_Kruskal(Edges, V, E):
    e=0, i=0
    sum=0
    Sort(Edges)
    while(e<V-1):
        u=Edges[i].u
        v=Edges[i].v
        if(Adding edge {u, v} do not form cycle):
            Print(Adding edge {u, v} to MST)
            sum+=Edges[i].weight
            e+=1
        i+=1

Code Example of C/C++, Python

To efficiently check whether including an edge forms a cycle or not, we will use an already discussed concept $i.e.$ Disjoint-Sets. We will proceed as per the pseudocode and algorithm discussed above, $i.e.$ firstly sorting the list of edges and then including $V-1$ edges that do not form cycles.
Find function of DSU will be used before including any edge in the MST to check if both the endpoints (nodes) of the edge belong to the same set or not.
If they do not belong to the same set, we will include that edge in the MST as including the edge is not forming any cycle. Now we will use the union function of DSU to merge the two disjoint sets.
Before going into the code, let’s see its blueprint –

Variables –

• $V$ – A global variable that will denote the number of vertices present in the graph.
• $E$ – Again a global variable denoting the count of edges present in the graph.
• $edges$ – A list of edges that will be sorted and then used in the Kruskal algorithm.

Method –

• $MST_Kruskal$ – A function that is responsible to find the MST of a given graph implemented as discussed in the algorithm and pseudocode.

Future-Proof Your Coding Skills! Join Our Best DSA Course for In-Depth Algorithmic Understanding. Enroll Now!

C/C++ Implementation of Kruskal’s Algorithm

#include<bits/stdc++.h>

using namespace std;
// Using DSU to quickly
// tell whether adding edge
// will form a cycle.
class DSU{

// Declaring two arrays to hold
// information about parent and 
// rank of each node. 
int *parent;
int *rank;

public:
// Constructor
DSU(int n){

    // Defining size of the arrays.
    parent=new int[n];
    rank=new int[n];

    // Initializing their values 
    // by is and 0s.
    for(int i=0;i<n;i++)
    {
        parent[i]=i;
        rank[i]=0;
    }
}

// Find function
int find(int node){

    // If the node is the parent of 
    // itself then it is the leader 
    // of the tree. 
    if(node==parent[node]) return node;

    //Else, finding parent and also 
    // compressing the paths.
    return parent[node]=find(parent[node]);
}

// Union function 
 void Union(int u,int v){

    // Make u as a leader 
    // of its tree.
    u=find(u);

    // Make v as a leader 
    // of its tree.
    v=find(v);

    // If u and v are not equal,
    // because if they are equal then
    // it means they are already in 
    // same tree and it does not make 
    // sense to perform union operation.
    if(u!=v)
    {
        // Checking tree with 
        // smaller depth/height.
        if(rank[u]<rank[v])
        {
            int temp=u;
            u=v;
            v=temp;
        }
        // Attaching lower rank tree
        // to the higher one. 
        parent[v]=u;

        // If now ranks are equal
        // increasing rank of u. 
        if(rank[u]==rank[v])
            rank[u]++;
    }
}

};
// Edge class
class Edge{
public:
// Endpoints and weight of the edge.
int u,v,weight;
// Constructor
Edge(int U,int V,int Weight){
u=U;
v=V;
weight=Weight;
}
};
class Graph{
public:
// Number of Vertices and Edges
int V, E;
// List of Edge(s).
vector edges;
// Constructor of Graph class
Graph(int v,int e){
V=v;
E=e;
// // Initializing list of edges.
// edges=new ArrayList<>();
}
// comparator to compare two edges
// based on their edges.
static bool comparator(Edge e1, Edge e2)
{
return e1.weight < e2.weight;
}
// Function responsible to print MST.
void MST_Kruskal(){
// Initializing e, i, and sum with 0.
int e=0,i=0,sum=0;
// Creating an object of DSU class.
DSU dsu(V);
// Sorting edges using a custom comparator
sort(edges.begin(), edges.end(), comparator);

    // Iterating till we include V-1 edges in MST
    while(e<V-1)
    {
        Edge edge=edges[i++];

        int u=dsu.find(edge.u);
        int v=dsu.find(edge.v);
        // Checking if adding edge with endpoints
        // u and v form a cycle.
        // If not
        if(u!=v)
        {
            cout<<"Adding edge "<<edge.u<<" <---> "<<edge.v<<" to MST\n";
            // Adding the weight of current edge to total
            // weight of the MST.
            sum+=edge.weight;
            // Including the edge.
            dsu.Union(u,v);
            // Increasing the edge count.
            e++;
        }
    }
    // Printing the total sum of the MST.
    cout<<"MST has a weight of "<<sum;
}
// Function to add edges.
void addEdge(int u,int v,int weight){
    edges.push_back(Edge(u,v,weight));
}

};
int main(){
// Creating an object of Graph type.
Graph g(6,9);

// Adding 9 edges to make the same
// graph as given in examples.
g.addEdge(0,1,7);
g.addEdge(0,2,8);
g.addEdge(1,2,3);
g.addEdge(1,4,6);
g.addEdge(2,3,3);
g.addEdge(2,4,4);
g.addEdge(3,4,2);
g.addEdge(3,5,2);
g.addEdge(4,5,2);

// Calling the MST_Kruskal Function.
g.MST_Kruskal();
return 0;

}

Java Implementation of `Kruskal’s Algorithm`

import java.util.*;
public class Graph{
// Using DSU to quickly
// tell whether adding edge
// will form a cycle.
static class DSU{

    // Declaring two arrays to hold
    // information about the parent and 
    // rank of each node. 
    private int parent[];
    private int rank[];

    // Constructor
    DSU(int n){

        // Defining size of the arrays.
        parent=new int[n];
        rank=new int[n];

        // Initializing their values 
        // with i's and 0s.
        for(int i=0;i<n;i++)
        {
            parent[i]=i;
            rank[i]=0;
        }
    }

    // Find function
    public int find(int node){

        // If the node is the parent of 
        // itself then it is the leader 
        // of the tree. 
        if(node==parent[node]) return node;

        //Else, finding parent and also 
        // compressing the paths.
        return parent[node]=find(parent[node]);
    }

    // Union function 
    public void union(int u,int v){

        // Make u as a leader 
        // of its tree.
        u=find(u);

        // Make v as a leader 
        // of its tree.
        v=find(v);

        // If u and v are not equal,
        // because if they are equal then
        // it means they are already in 
        // same tree and it does not make 
        // sense to perform union operation.
        if(u!=v)
        {
            // Checking tree with 
            // smaller depth/height.
            if(rank[u]<rank[v])
            {
                int temp=u;
                u=v;
                v=temp;
            }
            // Attaching lower rank tree
            // to the higher one. 
            parent[v]=u;

            // If now ranks are equal
            // increasing rank of u. 
            if(rank[u]==rank[v])
                rank[u]++;
        }
    }
}
// Edge class
static class Edge{
    // Endpoints and weight of the edge.
    int u,v,weight;
    // Constructor
    Edge(int u,int v,int weight){
        this.u=u;
        this.v=v;
        this.weight=weight;
    }
}
// Number of Vertices and Edges
static int V, E;
// List of Edge(s).
static List<Edge> edges;
// Constructor of Graph class
Graph(int V,int E){
    this.V=V;
    this.E=E;
    // Initializing list of edges.
    edges=new ArrayList<>();
}

// Function responsible to print MST.
static void MST_Kruskal(){
    // Initializing e, i and sum with 0.
    int e=0,i=0,sum=0;
    // Creating an object of DSU class. 
    DSU dsu=new DSU(V);
    // Sorting edges using a custom comparator
    Collections.sort(edges,
        new Comparator<Edge>(){
            public int compare(Edge e1,Edge e2){
                return e1.weight-e2.weight;
            }
        }
    );

    // Iterating till we include V-1 edges in MST
    while(e<V-1)
    {
        Edge edge=edges.get(i++);

        int u=dsu.find(edge.u);
        int v=dsu.find(edge.v);
        // Checking if adding edge with endpoints
        // u and v form a cycle.
        // If not
        if(u!=v)
        {
            System.out.println("Adding edge "+ edge.u +" <---> "+ edge.v +" to MST");
            // Adding the weight of current edge to total
            // weight of the MST.
            sum+=edge.weight;
            // Including the edge.
            dsu.union(u,v);
            // Increasing the edge count.
            e++;
        }
    }
    // Printing the total sum of the MST.
    System.out.println("MST has a weight of "+sum);
}
// Function to add edges.
static void addEdge(int u,int v,int weight){
    edges.add(new Edge(u,v,weight));
}
public static void main(String args[]){
    // Creating an object of Graph type.
    Graph g=new Graph(6,9);

    // Adding 9 edges to make the same
    // graph as given in examples.
    g.addEdge(0,1,7);
    g.addEdge(0,2,8);
    g.addEdge(1,2,3);
    g.addEdge(1,4,6);
    g.addEdge(2,3,3);
    g.addEdge(2,4,4);
    g.addEdge(3,4,2);
    g.addEdge(3,5,2);
    g.addEdge(4,5,2);

    // Calling the MST_Kruskal Function.
    g.MST_Kruskal();
}

}

Complexity Analysis

• Time Complexity –
  • Sorting of $E$ edges costs us $O(E*log(E))$ time.
  • For each edge, we are using the Union-Find algorithm which costs us $O(E*\alpha(V))$ time.
  • As discussed in DSU, for practical values of $V$, $i.e.$ $V\leq 10^{80}$ we can write $O(E*\alpha(V))$ as $O(E)$ because $O(\alpha(V))$ $\simeq$ $O(1)$.
  Hence, the overall time complexity is $O(Elog(E)+E)$ $\simeq$ $O(Elog(E))$
• Space Complexity – We are using a List/Vector to store the $E$ edges of the given graph so the space complexity is $O(E)$.

Applications of Kruskal’s Algorithm

MST's which can be found using the Kruskal algorithm has the following applications –

• In-network designing, finding MST tells you the minimum amount of wire needed to connect all the nodes (servers).
• Approximation of NP-Hard problems, like we can use MST to solve the traveling salesman problem.
• It is used in autoconfig protocol for ethernet bridging, which helps to avoid cycles in a network.
• All other graph theory problems where we need to visit all the vertices with minimum cost.

Become a master of data structures with our Data Structures in C++ Free Course. Start your journey today!

Conclusion

• In this article, we have learned what is meant by the spanning trees of a graph and what is the minimum spanning treewith the help of examples.
• We have seen Kruskal's algorithm which is a greedy algorithm to find an MST of any given weighted, undirected graph.
• At last, we have analyzed its time and complexity and space complexity and seen some of its major applications.