Working of Kruskal's Algorithm

Introduction

We shall talk about Kruskal's algorithm in this article. We shall also see Kruskal's algorithm's difficulty, functionality, example, and implementation in C++ as well. However, we should first comprehend the fundamental concepts, such as spanning tree and least spanning tree, before moving on to the technique.

The least spanning tree for a linked weighted graph is calculated using Kruskal's Algorithm. Finding the subset of edges that will let us pass through each graph vertex is the algorithm's main objective. It utilizes a greedy strategy that looks for the best result at each stage rather than focusing on a global optimum.

Working of Kruskal's Algorithm

Spanning tree - An undirected connected graph's subgraph is a spanning tree.

Minimum Spanning tree - The spanning tree with the lowest total edge weight is known as a minimum spanning tree. The spanning tree's weight is calculated by adding the weights assigned to its edges.

With Kruskal's algorithm, we begin with the edges that have the least weight and keep adding edges until we reach the desired result.

Steps to apply Kruskal's algorithm:

Sort all of the edges first from low weight to high weight.
Add the edge with the lightest weight to the spanning tree at this point. Reject the edge if it would otherwise result in a cycle.
A minimum spanning tree will be ready once all the edges are processed.

Dry Run Example

Let's now use an example to demonstrate how Kruskal's algorithm functions. An illustration will make it simpler to comprehend Kruskal's algorithm. Consider this weighted graph:-

The table below provides the edge weights for the graph above.

Edge	AB	AC	AD	AE	BC	CD	DE
Weight	1	7	10	5	3	4	2

Sort the edges listed above according to ascending weights.

Edge	AB	DE	BC	CD	AE	AC	AD
Weight	1	2	3	4	5	7	10

Let's begin building the smallest spanning tree.

Step 1 - Initialize the MST by adding the edge AB with weight 1.

Step 2 - As it is not producing the cycle, add the edge DE with weight 2 to the MST.

Step 3 - Since the edge BC with weight 3 does not produce a cycle or loop, add it to the MST.

Step 4 - The cycle is not being formed, therefore choose the edge CD with weight 4 to the MST at this time.

Step 5 - Pick the edge AE with weight 5 after that. This edge must be eliminated because including it will start the cycle.

Step 6 - Choose weight 7 and the edge AC. This edge must be eliminated because including it will start the cycle.

Step 7 - Choose AD with a weight of 10. Throwing away this edge will prevent the cycle from starting. As a result, the final minimal spanning tree created using Kruskal's approach from the provided weighted graph is -

The cost of the MST is = AB + DE + CD+ BC = 1 + 2 + 4 + 3 = 10.

The number of vertices in the tree above is now equal to the number of edges, minus 1. The algorithm ends here.

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];
void init()
{
for(int i = 0;i < MAX;++i)
id[i] = i;
}
int root(int x)
{
while(id[x] != x)
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}
void union1(int x, int y)
{
int p = root(x);
int q = root(y);
id[p] = id[q];
}
long long kruskal(pair<long long, pair<int, int> > p[])
{
int x, y;
long long cost, minimumCost = 0;
for(int i = 0;i < edges;++i)
{
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
if(root(x) != root(y))
{
minimumCost += cost;
union1(x, y);
}
}
return minimumCost;
}
int main()
{
int x, y;
long long weight, cost, minimumCost;
init();
cout <<"Enter Nodes and edges";
cin >> nodes >> edges;
for(int i = 0;i < edges;++i)
{
cout<<"Enter the value of X, Y and edges";
cin >> x >> y >> weight;
p[i] = make_pair(weight, make_pair(x, y));
}
sort(p, p + edges);
minimumCost = kruskal(p);
cout <<"Minimum cost is "<< minimumCost << endl;
return 0;
}

write your code here: Coding Playground

Output:

Enter Nodes and edges 57

Enter the value of X, Y, and edges 1 2 1

Enter the value of X, Y, and edges 1 3 7

Enter the value of X, Y, and edges 1 4 10

Enter the value of X, Y, and edges 1 5 5

Enter the value of X, Y, and edges 2 3 3

Enter the value of X, Y, and edges 3 4 4

Enter the value of X, Y, and edges 4 5 2

The minimum cost is 10

Complexity Analysis

The Kruskal algorithm has an O(E logE) or O(V logV) time complexity, where E is the number of edges and V is the number of vertices.

Applications:

Wiring between cities can be laid out using Kruskal's algorithm.
It is possible to use it to install LAN connections.