Boruvka’s algorithm for Minimum Spanning Tree in Python

Hello coders, In this tutorial, we are going to study about Boruvka’s algorithm in Python.

It is used to find the minimum spanning tree. First of all, let’s understand what is spanning tree, it means that all the vertices of the graph should be connected. It is known as a minimum spanning tree if these vertices are connected with the least weighted edges.

For the connected graph, the minimum number of edges required is E-1 where E stands for the number of edges. This algorithm works similar to the prims and Kruskal algorithms.

Borůvka’s algorithm in Python

Otakar Boruvka developed this algorithm in 1926 to find MSTs.

Algorithm 

  • Take a connected, weighted, and undirected graph as an input.
  • Initialize the vertices as individual components.
  • Initialize an empty graph i.e MST.
  • Do the following for each of them, while the number of vertices is greater than one.
    a) Find the least weighted edge which connects this vertex to any other vertex.
    b) Add the least weighted edge to the MST if not exists already.
  • Return the minimum spanning tree.

 

Source Code

from collections import defaultdict 

class Graph: 
# These are the four small functions used in main Boruvkas function
     # It does union of two sets of x and y with the help of rank
    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 #Make one as root and increment.
            rank[xroot] += 1

    def __init__(self,vertices): 
        self.V= vertices 
        self.graph = [] # default dictionary


    # add an edge to the graph 
    def addEdge(self,u,v,w): 
        self.graph.append([u,v,w]) 

    # find set of an element i 
    def find(self, parent, i): 
        if parent[i] == i: 
            return i 
        return self.find(parent, parent[i]) 

   
#***********************************************************************
    #constructing MST
    def boruvkaMST(self): 
        parent = [];
        rank = []; 
        cheapest =[]      
        numTrees = self.V 
        MSTweight = 0     
        for node in range(self.V): 
            parent.append(node) 
            rank.append(0) 
            cheapest =[-1] * self.V 

        # Keep combining components (or sets) until all 
        # compnentes are not combined into single MST 

        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] 

            # Consider the above picked cheapest edges and add them to MST 
            for node in range(self.V): 
                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 has weight %d is 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, 11) 
g.addEdge(0, 2, 5) 
g.addEdge(0, 3, 6) 
g.addEdge(1, 3, 10) 

g.boruvkaMST()

 

Output:

Edge 0-2 has weight 5 is included in MST
Edge 1-3 has weight 10 is included in MST
Edge 0-3 has weight 6 is included in MST
Weight of MST is 21

Now, lets us understand using an example:

Boruvka's algorithm in python

Find the least weighted edge for each vertex that connects it to another vertex, for instance.

Vertex                Cheapest Edge thatconnects
                                it to some other vertex

{0}                                     0-1
{1}                                      0-1
{2}                                     2-8
{3}                                     2-3
{4}                                     3-4
{5}                                     5-6
{6}                                     6-7
{7}                                     6-7
{8}                                     2-8

The edges with green markings are least weighted.boruvkas

Component                  Cheapest Edge that connects it
                                        to some other component

{0,1}                                           1-2 (or 0-7)

{2,3,4,8}                                      2-5

{5,6,7}                                         2-5

Now, repeat the above steps several times, as a result, we will get the least weighted edges.

boruvkas

After completing all the iterations we will get the final graph, i.e., minimum spanning tree MST.

 

In conclusion, we have understood how to create an MST of a connected, weighted graph, and also it is not very hard to create a minimum spanning tree.

Leave a Reply