# Kruskal’s Algorithm Minimum Spanning Tree Complete Guide

Are you looking to understand Kruskal’s Algorithm to construct a Minimum Spanning tree for any given undirected or directed graph? In this article, I will provide a complete guide with code to understand Kruskal’s Algorithm.

A spanning tree of a connected and undirected graph is a subgraph that is a tree that binds all of the vertices together. Many different spanning trees can exist in a single graph.

## What is Minimum Spanning Tree?

Minimum Spanning Tree for any undirected or directed graph is a spanning tree with a weightless than or equal to the weight of every other spanning tree.

The weight of a spanning tree is the sum of weights provided to each of the edges of a spanning tree.

The greedy technique is used by Kruskal’s algorithm to find the minimum cost spanning tree. This approach treats the graph as a forest, with each node representing a separate tree. A tree can only link to another tree if it has the lowest cost of all the choices and does not violate the MST characteristics.

### How many Minimum Edges does spanning Tree has?

To calculate the minimum number of edges for a spanning tree is easy. It has (V-1) where V is the number of vertices in the given graph.

Steps to find the Minimum Spanning Tree using Kruskal’s algorithm are as follows.

``````1. Arrange or Sort all of the edges in non-descending weight order.
2. Choose the smallest edge and Check to see if it forms a cycle with the spanning tree you've already created. Include this edge if a cycle isn't formed. Otherwise, toss it out.
3. Repeat step #2 until the spanning tree has (V-1) edges.]
Note: To perform step 2 you need to use Union-Find Algorithm for detection of Cycles. ``````

### Let us See the Pseudocode for Kruskal’s algorithm

Let us some up the Kruskal’s minimum spanning algorithm using pseudocode and then I will discuss its implementation with actual code.

``````Algorithm minimumSpanningTree(graph G)
S:= ∅
for each vertex v in G.V do
MAKE-SET(v)
for each (u, v) in G.E ordered by weight(u, v), in increasing
if FIND-SET(u) ≠ FIND-SET(v) then
add{(u,v)} to set S
UNION(FIND-SET(u), FIND-SET(v))
return S
S = set of Edges``````

## Working Code for Kruskal Algorithm

Let us see the working code implementation for Kruskal’s Algorithm in a real-world environment.

```#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// Defining a structure to store edge of the graph.
struct edge {
int source, dest, weight;
};

// Defining a Structure for comparision of edges based on weights.
struct compare
{
bool operator() (edge const &a, edge const &b) const {
return a.weight > b.weight;
}
};

// Creating a Class represeting disjoint set.
class disJointSet
{
unordered_map<int, int> main;
public:
// perform MakeSet operation on the given Graph
void makeSet(int N)
{
// create `N` disjoint sets (one for each vertex)
for (int i = 0; i < N; i++) {
main[i] = i;
}
}

// Find the root of the set in which element `k` belongs
int Find(int k)
{
// if `k` is root
if (main[k] == k) {
return k;
}

// recursion for the parent node until we find the root
return Find(main[k]);
}

// Perform Union of two subsets
void Union(int a, int b)
{
// find the root of the sets in which elements
// `x` and `y` belongs
int x = Find(a);
int y = Find(b);

main[x] = y;
}
};

// Function to construct S using Kruskal's algorithm
vector<edge> findKruskalSortPath(vector<edge> allEdges, int N)
{
// Initialize array s to stores the edges present in S
vector<edge> S;

// initialize `DisjointSet` class
disJointSet ds;

// create a singleton set for each element of the universe
ds.makeSet(N);

// sorting edges by increasing weight
sort(allEdges.begin(), allEdges.end(), compare());

// S contains exactly `V-1` edges
while (S.size() != N - 1)
{
// consider the next edge with minimum weight from the graph
edge next_edge = allEdges.back();
allEdges.pop_back();

// find the root of the sets to which two endpoints
// vertices of the next edge belongs
int x = ds.Find(next_edge.source);
int y = ds.Find(next_edge.dest);

// if both endpoints have different parents, they belong to
// different connected components and can be included in S
if (x != y)
{
S.push_back(next_edge);
ds.Union(x, y);
}
}
return S;
}

int main()
{
// vector of graph edges as per the above diagram.
vector<edge> allEdges =
{
// `(u, v, w)` triplet represent undirected edge from
// vertex `u` to vertex `v` having weight `w`
{ 0, 1, 7 }, { 1, 2, 8 }, { 0, 3, 5 }, { 1, 3, 9 },
{ 1, 4, 7 }, { 2, 4, 5 }, { 3, 4, 15 }, { 3, 5, 6 },
{ 4, 5, 8 }, { 4, 6, 9 }, { 5, 6, 11 }
};

// Assign Total number of Nodes in the Graph.
int N = 7;

// construct graph
vector<edge> e = findKruskalSortPath(allEdges, N);

for (edge &currentedge: e)
{
cout << "(" << currentedge.source << ", " << currentedge.dest << ", "
<< currentedge.weight << ")" << endl;
}

return 0;
}```

Output:

### Time Complexity:

For a graph with E edges and V vertices, Kruskal’s algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, all with simple data structures.

Where E is the number of the Edges and V is the number of vertices present in the graph.

That is all for Kruskal’s Algorithm. Let me know if you have any questions in the comment section. Also, let me know if you want the code in a different language as well.

And please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.