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

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.

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

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

You must be logged in to post a comment.