# Kruskal's Algorithm in Spanning Tree

**Minimum Spanning Tree**

A

minimum spanning tree(MST) orminimumweightspanning treeis a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with theminimumpossible total edge weight.

** Minimum Spanning Tree**

The above image is the example of **minimum spanning tree** . Let’s see the explanation of **minimum spanning tree**. See here number of nodes 10 and the number of edges are 21 .We will optimize this following graph so that more than two nodes do not create a circle and at the end, we will get the minimum **spanning tree **after adding the weight of selected edges. Please note that there is no single circle in the graph above (note the bold line). Just add the weight of the selective edges (bold), we will get our desired results.We can now discuss this spanning tree using the **Kruskal's** **algorithm **and will also see how we can find out the exact value from a **minimum spanning tree** .First we will point out the minimum weighted node such as

** After optimizing this tree **– Now** Minimum Spanning Tree**

The lowest weight in this graph above is 1 to 3 in the node . That is, the weight of this Edge is one . So we can start our traversing from node 1. From 1 to 4 or 1 to 2, we won't go there but we will go from 1 to 3 . Cause have to follow always the minimum weighted edge. Look at the top **graph **, they also did it . In this way, every node travels. And see, there is no cycle with one node to another after optimizing. This is the concept of **minimum spanning tree **.

**Prim's algorithm or Kruskal's**

One should use **Prim's algorithm **and when **Kruskal's** to find the **minimum spanning tree**? They both have easy logics, same worst cases, and only difference is implementation which might involve a bit different data structures. So what is the deciding factor . Use Prim's algorithm when you have a graph with lots of edgeFor a graph with **V** vertices **E** edges, **Kruskal's algorithm** runs in **O(E log V)** time and **Prim's algorithm **can run in **O(E + V log V)** amortized time, if you use a Fibonacci Heap.** Prim's algorithm** is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. **Kruskal** performs better in typical situations (sparse graphs) because it uses simpler data structures.

So keep in mind **Kruskal** time complexity worst case is **O(E log E)**,this because we need to sort the edges. **Prim** time complexity worst case is **O(E log V)** with **priority queue** or even better, **O(E+V log V)** with **Fibonacci Heap**. We should use Kruskal when the graph is sparse, i.e.small number of edges,like E=O(V),when the edges are already sorted or if we can sort them in linear time. We should use Prim when the graph is dense, i.e number of edges is high ,like E=O(V²). Of course we will solve minimum spanning tree problem using **prims algorithm **when the graph is **dense** . Prim's is faster than **Kruskal's** in the case of complex graphs.

**What is the difference betweenKruskal's and Prim's algorithm ?**

- • Prim’s algorithm initializes with a node, whereas Kruskal’s algorithm initiates with an edge.
- • Prim’s algorithms span from one node to another while Kruskal’s algorithm select the edges in a way that the position of the edge is not based on the last step.
- • In prim’s algorithm, graph must be a connected graph while the Kruskal’s can function on disconnected graphs too.
- • Prim’s algorithm has a time complexity of O(V^2), and Kruskal’s time complexity is O(logV).

Here i used **Kruskal's algorithm** to solve minimum spanning tree . See the source code .

**Source Code with Kruskal’s Algorithm**

If you have clear knowledge about **Ricursion**, **Disjoint Set ** and **Vector **of course you will understand my code. See this code which i used **Kruskal's algorithm**

```
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fathers[100];
int find(int x){
if(fathers[x]==x){
return x;
}
find(fathers[x]);
}
int main()
{
for(int i=0; i<100; i++)
fathers[i] = i;
int n,m;
int a,b,w;
vector < pair < int , pair < int ,int > > > edges;
cin>>n>>m;
for(int i=0; i<m; i++){
cin>>a>>b>>w;
edges.push_back(make_pair(w,make_pair(a,b)));
}
cout<<endl;
int mst_weight=0, mst_edges=0;
int mst_ni=0;
sort(edges.begin(),edges.end());
while( mst_ni < m )
{
a=edges[mst_ni].second.first;
b=edges[mst_ni].second.second;
w=edges[mst_ni].first;
int x,y;
x=find(a);
y=find(b);
if(x!=y){
fathers[x]=y;
mst_weight += w;
cout<<"connected " <<a<<" "<<b<<" "<<w<<endl;
}
mst_ni++;
}
cout<<"Minimum Spanning Tree Weight: "<<mst_weight<<endl<<endl;
for(int i=1; i<n; i++){
cout<<fathers[i]<<" ";
}
return 0;
}
```

That’s it. If you like this tutorial please leave a comments and share with your friends. If you find any error of this tutorial , please share this with me.

## Leave a comments