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

• 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 :

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.

#### 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;
}

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.