Boruvka’s algorithm for Minimum Spanning Tree in C++
By Dinesh KumarIn this tutorial, we are going to learn Boruvka’s algorithm for Minimum Spanning Tree in C++. Here we will learn about the spanning tree and Boruvka’s algorithm. After that, we will see the C++ program for the same.
Spanning Tree
A spanning tree is a subgraph of a graph G, which has all the vertices connected with the minimum possible edges. Hence, if the graph G contains v vertices than the spanning tree of G also contains v vertices and v-1 edges. Every connected and undirected Graph G has at least one spanning tree.
Minimum Spanning Tree
A connected and undirected graph may contain more than one spanning trees. A minimum spanning tree is the spanning tree that has the minimum total weight among all spanning trees of that graph. Let us see the example of spanning trees and minimum spanning tree.
In the above example, there are four spanning trees possible for the graph. And spanning tree-3 is the minimum spanning tree.
Boruvka’s Algorithm
Boruvka’s Algorithm is a greedy algorithm used for finding the minimum spanning tree of a weighted undirected graph. It was first given in 1926 by Otakar Boruvka as a method of constructing an efficient electricity network. This algorithm is also known as Sollin’s algorithm.
Boruvka’s Algorithm is slightly similar to Kruskal’s Algorithm.
In this algorithm, we have three main steps:-
1. We make a set of ‘v’ (total no. of vertices) trees, and each tree contains a single vertex. Or we can say each vertex is initially treated as an individual tree.
2. Use the smallest weighted outgoing edge from each tree to connect trees together.
3. Repeat the process until there is only one tree left. And this final tree is the minimum spanning tree.
Let us understand the algorithm with an example:-
In the above example, Figure-1 is the given graph and we have to find the minimum spanning tree using Boruvka’s algorithm. All the vertices are individual trees initially, and all of them are in different colors. In Figure-2, for each tree, we select the smallest-weighted outgoing edge and add connect the corresponding affected tree. Vertex-1 has three outgoing edges and 3 is the smallest weighted edge that connects to vertex-2. Similarly, vertex-4 connect to vertex-1 and vertex-3 connects to vertex-5. So, finally, it contains two trees pink and green. This step is repeated until only one tree is left. In Figure-3, the two trees pink and green are connected by edge 8 that connect vertex-3 and vertex-4 and finally we get a single tree and that is our minimum spanning tree.
Algorithm:-
1. Initialize a forest T that contains one vertex-trees, one for each vertex of the graph. 2. while size(T) > 1 3. for each element C of T 4. create an empty set of edges S; 5. for each vertex 'v' ∈ C 6. Find the least weight edge 'e' from v to a vertex u ∉ C; 7. Add 'e' into S; 8. Add the smallest weighted edge 'e' ∈ S to T; 9. T is the final minimum spanning tree of the given graph. 10. Display output T.
C++ program for Boruvka’s Algorithm
So, here is the C++ implementation of the above algorithm. This algorithm uses disjoint-set-union data structure.
#include<bits/stdc++.h>
using namespace std;
/*==================================================
DSU FIND FUNCTION (path compression)
===================================================*/
int find(vector<pair<int,int>>&trees, int i)
{
// find root and make root as parent of i
if (trees[i].second != i)
trees[i].second = find(trees, trees[i].second);
return trees[i].second;
}
/*====================================================
DSU UNION FUNCTION (union by comparing rank)
=====================================================*/
void Union(vector<pair<int,int>>&trees, int a, int b)
{
int rootA = find(trees, a);
int rootB = find(trees, b);
// merge smaller tree to larger one by comparing rank
if (trees[rootA].first < trees[rootB].first)
trees[rootA].second = rootB;
else if (trees[rootA].first > trees[rootB].first)
trees[rootB].second = rootA;
// If ranks are same
else
{
trees[rootB].second = rootA;
trees[rootA].first++;
}
}
/*========================================================
BORUVKA'S ALGORITHM MAIN FUNCTION
=========================================================*/
void Boruvkas_function(vector<vector<int>>Graph,int V,int E)
{
//Create a vector of pairs for V different trees.
//Pair is used for storing rank and parent (DSU)
vector<pair<int,int>>trees;
// Create V single-vertex trees
for (int i = 0; i < V; i++)
{
trees.push_back(make_pair(0,i));
}
//Initialising two variables
//TotalTrees stores total no. of trees
//MST_total_weight stores total weight of MST
int TotalTrees = V;
int MST_total_weight = 0;
cout<<"Edges of MST are :-"<<endl;
//Loop till only one tree(MST) left
while (TotalTrees > 1)
{
//A vector is created to store smallest edge
//of each tree. And initialised to -1
vector<int> smallest_edge(V,-1);
// Traverse through all edges and update
// smallest_edge of every tree
for (int i=0; i<E; i++)
{
// Find trees of vertices(s-d) of current edge
int setA = find(trees, Graph[i][0]);
int setB = find(trees, Graph[i][1]);
// If two vertices of current edge belong to
//same tree -->continue
if (setA == setB)
continue;
// Else check if current edge is closer to previous
// smallest_edge edges of setA and setB
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;
}
}
//Add edges to MST
for (int i=0; i<V; i++)
{
//if smallest_edge for current set exists
if (smallest_edge[i] != -1)
{
int setA=find(trees, Graph[smallest_edge[i]][0]);
int setB=find(trees, Graph[smallest_edge[i]][1]);
//if they belong to same tree -->continue
if (setA == setB)
continue;
//calculate the total weight of MST
MST_total_weight += Graph[smallest_edge[i]][2];
//Displaying output edges of final MST
cout<<"Edge ("<<Graph[smallest_edge[i]][0]<<","
<<Graph[smallest_edge[i]][1]<<") "<<"weight "
<<Graph[smallest_edge[i]][2]<<endl;
//If two trees are not same then do the union
//and decrement the no. of trees
Union(trees, setA, setB);
TotalTrees--;
}
}
}
//Displaying Total weight of MST
cout<<"Total weight of MST is:"<<MST_total_weight<<endl;
}
/*======================================
MAIN FUNCTION
=======================================*/
int main()
{
/* GIVEN GRAPH
3
1-------------2
| \ 13 |
| \ |
| 5 |
4| \ |9
| \ 2 |
| \ |
4-------------3
8 */
int V = 5; // Number of vertices
int E = 6; // Number of edges
//Creating 2D vector for graph
vector<vector<int>>Graph;
//Inserting edge (1,2) weight:3
Graph.push_back({1,2,3});
//Inserting edge (1,4) weight:4
Graph.push_back({1,4,4});
//Inserting edge (1,5) weight:13
Graph.push_back({1,5,13});
//Inserting edge (2,3) weight:9
Graph.push_back({2,3,9});
//Inserting edge (5,3) weight:2
Graph.push_back({5,3,2});
//Inserting edge (3,4) weight:8
Graph.push_back({3,4,8});
//Calling Boruvkas_function()
Boruvkas_function(Graph,V,E);
return 0;
}
Output:-
Edges of MST are:- Edge (5,3) weight 2 Edge (1,2) weight 3 Edge (1,4) weight 4 Edge (3,4) weight 8 Total weight of MST is:17
Thanks for reading this tutorial. I hope it helps you !!
Leave a Reply