Krushkal’s algorithm – Minimum Spanning Tree (MST)

Arunima Mandal

Note:

It’s a greedy approach. Basically, there are 3 steps in Krushkal’s algorithm.

  1. Sort the edges according to their cost in ascending order.
  2. Traverse through the sorted edges list upto n-1 length
    • a.If the edge creates a loop(use Find or Union of Union-Find to check the loop), do not consider it.
    • b. else add it to the MST list by using Union and add the cost of the edge to the answer.

Time Complexity:

O(ElogE) where E is the number of edges.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(root[x]==x) return x;
    return root[x]=Find(root[x], root);
}

void Union(int x, int y, vector<int> &root, vector<int> &rankk)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(rankk[rootX]>=rankk[rootY]) root[rootY]=rootX;
        else if(rankk[rootY]>=rankk[rootX]) root[rootX]=rootY;
        else
        {
            root[rootY]=rootX;
            rankk[rootX]++;
        }
    }
}

int Krushkals(vector<vector<int>> &edges, int n)
{
    sort(edges.begin(), edges.end());
    vector<int> root(n+1);
    vector<int> rankk(n+1);
    for(int i=0; i<n; i++)
    {
        root[i]=i;
        rankk[i]=1;
    }
    int ans=0, groups=0;
    for(int i=0; i<edges.size() && groups<n-1; i++)
    {
        int x=edges[i][1];
        int y=edges[i][2];
        int cost=edges[i][0];
        if(Find(x, root)!=Find(y, root)) //if no cycle exists
        {
            Union(x,y,root, rankk);
            ans+=cost;
            groups++;
        }
    }
    return ans;

}

int main()
{
    int n,m;
    vector<vector<int> > edges;
    cout<<"Enter the no. of nodes in the graph: ";
    cin>>n;
    cout<<"Enter the no. of edges: ";
    cin>>m;
    cout<<"Enter the and their corresponding cost (node node cost):"<<endl;
    for(int i=0; i<m; i++)
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        edges.push_back({cost, x, y});
    }
    int ans=Krushkals(edges, n);
    cout<<"The minimum cost for traversing all the nodes once: "<<ans<<endl;
    return 0;
}
/*
Sample input:
5
7
0 1 1
0 2 2
0 3 3
1 2 2
2 3 3
3 4 4
4 0 5

Sample Output:
10

Note: Minimum spanning tree formed by nodes 0-1-2-3-4

*/

Leave a comment