Boruvkas algorithm
This algorithm is used for finding minimum spanning tree from a weighted graph. Like prim’s and kruskal’s algorithm it is also a greedy algorithm.
Note:
What is the minimum spanning tree?
We know that tree is also a special type of graph. We can build a tree from graphs. Now if the graph is weighted then we can form a tree from this graph so that the weight will be minimum. This tree is called minimum spanning tree. There are many algorithms to build this tree. Boruvkas algorithm is one of them.
Algorithm
In this algorithm we will use the approach which we used in prim’s algorithm. Let’s look at the steps of algorithm.
Step 1: Start
Step 2: Graph is taken from the user.
Step 3: Now we imagine every vertex as an individual component.
Step 4: We connects the component by closest vertex of other component whose weight is minimum.
Step 5: Connecting ways are stored. Now it is obvious that there will be same connecting edges for more components. So, we will take only one. The remaining components will be connected in next comparison.
Step 6: Remaining components will be connected by closest and lowest weight vertex of another component.
Step 7: this process will continue till we don’t get the minimum spanning tree.
Step 8: The answer will be printed.
Step 9: Stop.
Code:
# Forming minimum spanning tree using Boruvkas algorithm from a connected weighted graph
from collections import defaultdict
#declaration of graph class to represent the graph
class Graph:
def __init__(self,vertices):
self.V= vertices #representation of the number of vertices
self.graph = [] # default dictionary to store graph
# declaration of a function for adding a new edge in the graph
def addEdge(self,u,v,w):
self.graph.append([u,v,w])
# this function will find a set of element
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else :
parent[yroot] = xroot
rank[xroot] += 1
# This is the driver function to construct minimum spanning tree using boruvka's algorithm
def boruvkaMST(self):
parent = []; rank = [];
# we declare the array to store index of the cheapest edge of subset
cheapest =[]
numTrees = self.V
MSTweight = 0
for node in range(self.V):
parent.append(node)
rank.append(0)
cheapest =[-1] * self.V
while numTrees > 1:
for i in range(len(self.graph)):
u,v,w = self.graph[i]
set1 = self.find(parent, u)
set2 = self.find(parent ,v)
if set1 != set2:
if cheapest[set1] == -1 or cheapest[set1][2] > w :
cheapest[set1] = [u,v,w]
if cheapest[set2] == -1 or cheapest[set2][2] > w :
cheapest[set2] = [u,v,w]
for node in range(self.V):
#here we check whether it is cheapest for current set exists
if cheapest[node] != -1:
u,v,w = cheapest[node]
set1 = self.find(parent, u)
set2 = self.find(parent ,v)
if set1 != set2 :
MSTweight += w
self.union(parent, rank, set1, set2)
print ("Edge %d-%d with weight %d included in MST" % (u,v,w))
numTrees = numTrees - 1
cheapest =[-1] * self.V
print ("Weight of MST is %d" % MSTweight)
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
g.boruvkaMST()
//C++ program for Boruvka’s algo
#include<bits/stdc++.h>
using namespace std;
int find(vector<pair<int,int>>&trees, int i)
{
if (trees[i].second != i)
trees[i].second = find(trees, trees[i].second);
return trees[i].second;
}
void Union(vector<pair<int,int>>&trees, int a, int b)
{
int rootA = find(trees, a);
int rootB = find(trees, b);
if (trees[rootA].first < trees[rootB].first)
trees[rootA].second = rootB;
else if (trees[rootA].first > trees[rootB].first)
trees[rootB].second = rootA;
else
{
trees[rootB].second = rootA;
trees[rootA].first++;
}
}
void Boruvkas_function(vector<vector<int>>Graph,int V,int E)
{
vector<pair<int,int>>trees;
for (int i = 0; i < V; i++)
{
trees.push_back(make_pair(0,i));
}
int TotalTrees = V;
int MST_total_weight = 0;
cout<<"Edges of MST are :-"<<endl;
while (TotalTrees > 1)
{
vector<int> smallest_edge(V,-1);
for (int i=0; i<E; i++)
{
int setA = find(trees, Graph[i][0]);
int setB = find(trees, Graph[i][1]);
if (setA == setB)
continue;
else
{
if (smallest_edge[setA] == -1 ||
Graph[smallest_edge[setA]][2] > Graph[i][2])
smallest_edge[setA] = i;
if (smallest_edge[setB] == -1 ||
Graph[smallest_edge[setB]][2] > Graph[i][2])
smallest_edge[setB] = i;
}
}
for (int i=0; i<V; i++)
{
if (smallest_edge[i] != -1)
{
int setA=find(trees, Graph[smallest_edge[i]][0]);
int setB=find(trees, Graph[smallest_edge[i]][1]);
if (setA == setB)
continue;
MST_total_weight += Graph[smallest_edge[i]][2];
cout<<"Edge ("<<Graph[smallest_edge[i]][0]<<","
<<Graph[smallest_edge[i]][1]<<") "<<"weight "
<<Graph[smallest_edge[i]][2]<<endl;
Union(trees, setA, setB);
TotalTrees--;
}
}
}
cout<<"Total weight of MST is:"<<MST_total_weight<<endl;
}
int main()
{
int V = 5; // Number of vertices
int E = 6; // Number of edges
vector<vector<int>>Graph;
Graph.push_back({1,2,3});
Graph.push_back({1,4,4});
Graph.push_back({1,5,13});
Graph.push_back({2,3,9});
Graph.push_back({5,3,2});
Graph.push_back({3,4,8});
Boruvkas_function(Graph,V,E);
return 0;
}
Output:
Edge 0-3 with weight 5 included in MST
Edge 0-1 with weight 10 included in MST
Edge 2-3 with weight 4 included in MST
Weight of MST is 19
Complexity Analysis
Time complexity: The time complexity of Boruvkas algorithm is O (Elogv ). Here E represents number of edges and v represents number of vertices.