Boruvka’s algorithm for Minimum Spanning Tree in Python
By Jaspreet SinghHello 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