Kruskals Algorithm

---

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.

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

1. Sort all the edges in non-decreasing order of their weights.
2. 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.
3. 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.