Boruvka’s algorithm for Minimum Spanning Tree in C++

In 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.

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:-

Boruvka's Algorithm

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

Your email address will not be published. Required fields are marked *