Krushal’s Algorithm

What is Krushal's Algorithm?

The purpose behind Krushal’s algorithm is to find a minimum spanning forest of an undirected edge-weighted graph. For instance, if the graph is connected, it will find a minimum spanning tree.

Now, a Minimum Spanning Tree or MST in Krushal’s algorithm refers to the path joining vertices of a graph in such a way that all the vertices/nodes are connected and there is no cycle present in the graph i.e. we cannot visit a vertex/node more than once.

Let us consider this graph with some edge weights given as:

So, for the above graph our Minimum Spanning Tree will look like this:

Hence the smallest cost of the path is the sum of the above edge weights i.e. 6 which is minimum and hence it is called the minimum spanning tree. Now to approach this algorithm we need to discuss a few concepts before moving forward with Disjoint Set data structure, although only a brief discussion will be given here.

Must Read, floyd's algorithm

Check This Out, binary search algorithm

Disjoint Set Data Structure

A set can be simply implemented using an array & the equivalence of their subsets can be found. Let us assume we have a set S of various elements. Now for every element a, b ϵ S, we define some relations over these elements.

This implementation involves three methods:

• MAKESET(X) (creates a set with element X).
• FIND(X) (find the name of the equivalence set which contains X).
• UNION(X,Y) (Union the two sets X,Y to create a new set containing all the elements X,Y and deleting the previous sets of X,Y.

In simple terms FIND function finds and returns the parent of an element and UNION function joins both the sets if their parents are different. Let us now see their code implementation.

int FIND(int parent[],int size,int x){
if(!(x>=0 && x < size)) return -1; if(parent[x] == x) // if the parent is itself return that element return x; else return FIND(parent,size,parent[x]); // recursively call on the parent } Void UNION(int parent[],int size,int root1,int root2){ If(FIND(parent,size,root1) == FIND(parent,size,root2)) // check if their parents are same Return; If(!((root1 >= 0 && root1 < size) && (root2 >= 0 && root2 <size)))
Return;
parent[root1] = parent[root2]; // if their parents are not the same the simply make one parent of each other so that the two disjoint sets are combined.
}

Although both the algorithm runs in time which is too costly when we are talking about a large number of sets. In Kruskal’s algorithm, we might need this code to run for thousands of vertices as nodes of the sets which becomes very expensive in terms of time. Hence to reduce this time complexity we use Find by path compression and Union by rank compression.

Let us see their implementation now:

int find(ll i){
if(parent[i] == -1)return i;
return parent[i] = find(parent[i]); // making their parent as own

void unite(int x,int y){
    int s1 = find(x);
    int s2 = find(y);
    if(s1!=s2){
        if(rank[s1] < rank[s2]){
            parent[s1] = s2;
            rank[s2] += rank[s1];    //compress by joining the smaller rank set to larger set
        }else{
            parent[s2] = s1;
            rank[s1] += rank[s2];
        }
    }

}

These two implementations reduced the time complexity to nearly constant time i.e. Now let us see the algorithm of Kruskal’s Minimum Spanning Tree.

• Sort the edges in ascending order of their weights/cost.
• Iterate through the edges now and check if they belong to different sets then combine them and connect the edge by adding the weight to our answer else if the parents are same then continue.
• At the end of the above steps, we will have our answer as the minimum spanning tree cost and the connected nodes/vertices using union-find.

Code Implementation:

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
class DSU{
ll *parent;
ll *rank;
ll V;
public:
DSU(ll v){
this->V = v;
parent = new ll[V];
rank = new ll[V];
for(ll i = 0;i > edgeList;
public:
Graph(ll v){
this->V = v;
}
void addEdge(ll u,ll v,ll w){
edgeList.push_back({w,u,v});
}
ll kruskal(){
ll ans = 0;
sort(edgeList.begin(),edgeList.end());
DSU dsu(V);
for(auto edge : edgeList){
ll w = edge[0];
ll x = edge[1];
ll y = edge[2];
if(dsu.find(x)!=dsu.find(y)){
dsu.unite(x,y);
ans += w;
}
}
return ans;
}

};
int main() {
ll n;
cin>>n;
Graph g(n);
ll m;
cin>>m;
for(ll i =0;i>x>>y>>w;
g.addEdge(x-1,y-1,w);
}
cout<<g.kruskal()<<endl;
}

Now let us see the applications and some questions of Kruskal’s algorithm- For a given graph G with N vertices and M edges, where wi denotes the weight of the i-th edge, the goal is to remove at mostK edges from G producing a new graph G, in such a way that G is connected and the weight of the minimum spanning tree of G is maximised.

Solution:

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int main(void) {
int n, m, k; cin >> n >> m >> k;
cout << m << endl; for (int i = 1; i <= m; ++i) cout << i << ‘ ‘; cout << endl; return 0; Considering an edge class/structure struct Edge { int a, b, c, i; bool operator < (const Edge& that) const { return c < that.c; } }; vector e(m);
for (int i = 0; i < m; ++i) { cin >> e[i].a >> e[i].b >> e[i].c;
e[i].i = i + 1;
}
sort(e.begin(), e.end());
vector rt(n + 1), ht(n + 1);
function rof = [&](int x) {
return x == rt[x] ? x : (rt[x] = rof(rt[x]));
};
for (int x = 1; x <= n; ++x) { rt[x] = x; } vector d;
for (int i = m; i– > 0; ) {
int a = rof(e[i].a), b = rof(e[i].b);
if (a != b) {
if (ht[a] < ht[b]) { swap(a, b); } rt[b] = a; ht[a] = max(ht[a], ht[b] + 1); } else { d.push_back(e[i]); } } sort(d.begin(), d.end()); vector f(n + 1);
cout << (m – min(k, (int)d.size())) << ‘\n’;
for (int i = 0; i < k && i < d.size(); ++i) {
f[d[i].i] = true;
}
for (int x = 1; x <= n; ++x) {
if (!f[x]) {
cout << x << ‘ ‘;
}
}
cout << ‘\n’;

return 0;

}