Kruskal’s Algorithm
Welcome guys! In this blog I will talk about Kruskal’s Algorithms, a minimum spanning tree (MST) or minimum weight spanning tree, how Kruskal’s algorithm works and where we use it, and its application. As you know it is one of the most imps. Algo of DSA (Data Structure and Algorithm) So let’s get started.
Firstly we will talk about
“What is Kruskal’s Algorithm?”
Kruskal’s Algorithm is an algorithm that is used to find a minimum cost spanning tree or minimum spanning tree(MST) in Graph. This Algo. uses a greedy approach. There is one more algorithm ( “Prim’s Algorithm“ ) that is also used to find MST But if you understand this, then you can do that too easily. Now we will move on to understand the topic,
Now I will give you a brief description of Spanning Tree so that you can understand MST obviously if you do not know Spanning Tree you can’t understand MST,
Spanning Tree: A connected subgraph ‘S’ of graph G(V, E) where V is the number of vertices and E is the number of edges, is said to be a spanning tree if,
- ‘S’ should contain all vertices of G(V, E).
- ‘S’ should contain (|V|-1) edges.
Complete graph: every node is connected to each node of the graph then the graph is called a complete graph.
We found three spanning trees off one complete graph. A complete undirected graph can have a maximum n^(n-2) number of spanning trees, where n is the number of nodes. In the above-addressed example, n is 3, hence 3^(3−2) = 3 spanning trees are possible.
But if a graph is not complete then you have to draw all.
So back to our main topic which is to find MST using Kruskal’s Algorithm. We had seen the spanning Tree, now is the time to know MST (Minimum Spanning Tree or Minimum Cost Spanning Tree)
What is the Minimum spanning tree (MST)?
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
By this definition, we can reach an inference that each associated and undirected Chart G has in any event one spanning tree. A detached chart doesn’t have any spanning tree, as it can’t be spread over to all its vertices.
Steps to find MST using Kruskal’s algorithm?
This algorithm falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of finding a global optimum
Step 1: Draw all vertices.
So that you can do the steps which I will be giving in upcoming lines.
Step 2: Sort edge weights in nondecreasing order.
Step 3: Take the edge with the most minimal weight and add it to the spanning tree. On the off chance that adding the edge made a cycle, reject this edge.
Step 4: Continue to add edges until we cover all vertices.
Let’s take an example so that you can understand it easily:
Graph :
Now we have to find MST using Kruskal’s Algorithm :
Step 1: Draw all vertices.
In above image we had drawn a skeleton of our graph.
Step 2: Sort edge weights in nondecreasing order.
In the above image, we sorted all edge weights in nondecreasing order.
Step 3: Take the edge with the most minimal weight and add it to the spanning tree. On the off chance that adding the edge made a cycle, reject this edge.
In the above Image, As we had chosen minimum edge weight ‘2’ (BE),
In the above Image, Now for the next minimum, we can choose any edge of the weight of 3 (EF or AC) as non of them is completing a cycle. So I had shown you both but in the upcoming steps, I will going to show you any one and other you can do by yourself.
In the above Image as we go to the next minimum after choosing one from EF or AC then that is also 3 so we choose the next 3 weight edge considering that it wouldn’t form a cycle.
In the above image, as we proceed to the next minimum which is an edge of weight 4 (FG, BC, EG) here you can choose anyone. here we had chosen FG you can do with any of them answer will be the same in the end.
In the above Image, after we had chosen FG now we had 2 edges of weight 4 (BC, EG) which is the next minimum. Here we couldn’t choose EG as it is completing a cycle which is not possible therefore we can only choose BC.
In the above Image, after choosing BC we can not choose EG as it will complete therefore we have to discard it and move to the next minimum which is 5, As there are 2 edges of weight 5 (AB and CD) but here we can’t choose AB as it will too complete cycle and after this, we can not choose any edge as every edge will complete cycle. and both the rules of the Spanning tree are satisfied by the above diagram there this will be our final MST and for Minimum cost, you have to add weights of all edges chosen.
So here we had completed Kruskal’s Algorithm.
Now we will see the Pseudocode code for Kruskal’s Algorithm.
Pseudocode Kruskal’s Algorithm :
KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A// Kruskal's algorithm in C++
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define edge pair<int, int>
class Graph {
private:
vector<pair<int, edge> > G; // graph
vector<pair<int, edge> > T; // mst
int *parent;
int V; // number of vertices/nodes in graph
public:
Graph(int V);
void AddWeightedEdge(int u, int v, int w);
int find_set(int i);
void union_set(int u, int v);
void kruskal();
void print();
};
Graph::Graph(int V) {
parent = new int[V];
//i 0 1 2 3 4 5
//parent[i] 0 1 2 3 4 5
for (int i = 0; i < V; i++)
parent[i] = i;
G.clear();
T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {
// If i is the parent of itself
if (i == parent[i])
return i;
else
// Else if i is not the parent of itself
// Then i is not the representative of his set,
// so we recursively call Find on its parent
return find_set(parent[i]);
}
void Graph::union_set(int u, int v) {
parent[u] = parent[v];
}
void Graph::kruskal() {
int i, uRep, vRep;
sort(G.begin(), G.end()); // increasing weight
for (i = 0; i < G.size(); i++) {
uRep = find_set(G[i].second.first);
vRep = find_set(G[i].second.second);
if (uRep != vRep) {
T.push_back(G[i]); // add to tree
union_set(uRep, vRep);
}
}
}
void Graph::print() {
cout << "Edge :"
<< " Weight" << endl;
for (int i = 0; i < T.size(); i++) {
cout << T[i].second.first << " - " << T[i].second.second << " : "
<< T[i].first;
cout << endl;
}
}
int main() {
Graph g(6);
g.AddWeightedEdge(0, 1, 4);
g.AddWeightedEdge(0, 2, 4);
g.AddWeightedEdge(1, 2, 2);
g.AddWeightedEdge(1, 0, 4);
g.AddWeightedEdge(2, 0, 4);
g.AddWeightedEdge(2, 1, 2);
g.AddWeightedEdge(2, 3, 3);
g.AddWeightedEdge(2, 5, 2);
g.AddWeightedEdge(2, 4, 4);
g.AddWeightedEdge(3, 2, 3);
g.AddWeightedEdge(3, 4, 3);
g.AddWeightedEdge(4, 2, 4);
g.AddWeightedEdge(4, 3, 3);
g.AddWeightedEdge(5, 2, 2);
g.AddWeightedEdge(5, 4, 3);
g.kruskal();
g.print();
return 0;
}
Now , At last lets see the time complexity of Kruskal’s Algorithm .
Time Complexity :
O(E log V)
Kruskal’s algorithm’s time complexity is O(E log V), V being the number of vertices.
Thank You.