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 beV-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.