Today i will explain the full implementation and working of Kruskals algorithm by using an example dry run of the code and finally the code explanation.In this aticle, i have shown implementation of kruskal algo using disjoint set union by rank and path compression algorithm.In the dry run, i have not explained path compression find algorithm to reduce complexity of understanding.All the related USEFUL video links are present below.

*Let’s start with the basic points to ponder :*

- Kruskals algorithm is a greedy algorithm
- If we have
`V`

no of vertices, then the no. of edges in the MST(Minimum Spanning Tree) will be`V-1`

. - MST can be formed for connected graphs only.

The given graph will look like this with V-1 vertices as MST.

Now, let’s see the steps to construct the MST :

- Sort all the edges in non-decreasing order of their weights.
- Now,

2.1) Pick the smallest edge.

2.2) Check if this newly added edge will form a cycle in our spanning tree or not.

If no cycle is formed, then we will simply include this edge, else discard this edge. - Repeat step 2 until
`V-1`

edges are included in the MST.

**Watch this concise video for better explanation of the above steps with example.**

Now, after working on the above steps, our MST will(say) look like this.

Here is the video for implementation of Kruskals algorithm with code using Disjoint Set Union(DSU).

#### CODE:

#include<bits/stdc++.h> using namespace std; struct node { int parent; int rank; }; struct Edge { int src; int dst; int wt; }; vector<node> dsuf; vector<Edge> mst; //FIND operation int find(int v) { if(dsuf[v].parent==-1) return v; return dsuf[v].parent=find(dsuf[v].parent); //Path Compression } void union_op(int fromP,int toP) { //fromP = find(fromP); //toP = find(toP); //UNION by RANK if(dsuf[fromP].rank > dsuf[toP].rank) //fromP has higher rank dsuf[toP].parent = fromP; else if(dsuf[fromP].rank < dsuf[toP].rank) //toP has higher rank dsuf[fromP].parent = toP; else { //Both have same rank and so anyone can be made as parent dsuf[fromP].parent = toP; dsuf[toP].rank +=1; //Increase rank of parent } } bool comparator(Edge a,Edge b) { return a.wt < b.wt; } /* void printEdgeList(vector<Edge>& edge_List) { for(auto p: edge_List) cout<<"src: "<<p.src<<" dst: "<<p.dst<<" wt: "<<p.wt<<"\n"; cout<<"============================================================\n"; } */ void Kruskals(vector<Edge>& edge_List,int V,int E) { //cout<<"edge_List before sort\n"; //printEdgeList(edge_List); sort(edge_List.begin(),edge_List.end(),comparator); //cout<<"edge_List after sort\n"; //printEdgeList(edge_List); int i=0,j=0; while(i<V-1 && j<E) { int fromP = find(edge_List[j].src); //FIND absolute parent of subset int toP = find(edge_List[j].dst); if(fromP == toP) { ++j; continue; } //UNION operation union_op(fromP,toP); //UNION of 2 sets mst.push_back(edge_List[j]); ++i; } } //Display the formed MST void printMST(vector<Edge>& mst) { cout<<"MST formed is\n"; for(auto p: mst) cout<<"src: "<<p.src<<" dst: "<<p.dst<<" wt: "<<p.wt<<"\n"; } int main() { int E; //No of edges int V; //No of vertices (0 to V-1) cin>>E>>V; dsuf.resize(V); //Mark all vertices as separate subsets with only 1 element for(int i=0;i<V;++i) //Mark all nodes as independent set { dsuf[i].parent=-1; dsuf[i].rank=0; } vector<Edge> edge_List; //Adjacency list Edge temp; for(int i=0;i<E;++i) { int from,to,wt; cin>>from>>to>>wt; temp.src = from; temp.dst = to; temp.wt = wt; edge_List.push_back(temp); } Kruskals(edge_List,V,E); printMST(mst); return 0; } //TIME COMPLEXITY: O(ElogE + ElogV) //ElogE for sorting E edges in edge_list //ElogV for applying FIND & UNION operations on E edges having V vertices

Time Complexity: (ElogE + ElogV)

*ElogE* is the time for sorting E no. of edges and for each edges we include, and check if any cycle is formed in logV time for each edges using DSUF.

While finding the cycle, we use *DSUF(Disjoin Set Union Find) using union by rank and path compression algorithm.*