In this post, Boruvka’s algorithm is discussed. Like Prim’s and Kruskal’s, Boruvka’s algorithm is also a Greedy algorithm. Below is complete algorithm.

1) Input is a connected, weighted and directed graph.
2) Initialize all vertices as individual components (or sets).
3) Initialize MST as empty.
4) While there are more than one components, do following
   for each component.
      a)  Find the closest weight edge that connects this 
          component to any other component.
      b)  Add this closest edge to MST if not already added.  
5) Return MST.

Below is the idea behind above algorithm (The idea is same as Prim’s MST algorithm).

A spanning tree means all vertices must be connected. So the two disjoint subsets (discussed above) of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.

[ad type=”banner”]

Let us understand the algorithm with below example.

Boruvka’s algorithm

Initially MST is empty. Every vertex is singe component as highlighted in blue color in below diagram.

Boruvka’s algorithm

For every component, find the cheapest edge that connects it to some other component.

Component                Cheapest Edge that connects 
                         it to some other component
  {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 cheapest edges are highlighted with green color

Boruvka’s algorithm

After above step, components are {{0,1}, {2,3,4,8}, {5,6,7}}. The components are encircled with blue color.Boruvka’s algorithm

We again repeat the step, i.e., for every component, find the cheapest edge that connects it to some other component.

[ad type=”banner”]
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

The cheapest edges are highlighted with green color. Now MST becomes

Boruvka’s algorithm

At this stage, there is only one component {0, 1, 2, 3, 4, 5, 6, 7, 8} which has all edges. Since there is only one component left, we stop and return MST.

Implementation:
Below is implementation of above algorithm. The input graph is represented as a collection of edges and union-find data structure is used to keep track of components.

python programming:

[pastacode lang=”python” manual=”%23%20Boruvka’s%20algorithm%20to%20find%20Minimum%20Spanning%0A%23%20Tree%20of%20a%20given%20connected%2C%20undirected%20and%20weighted%20graph%0A%20%0Afrom%20collections%20import%20defaultdict%0A%20%0A%23Class%20to%20represent%20a%20graph%0Aclass%20Graph%3A%0A%20%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20%5B%5D%20%23%20default%20dictionary%20to%20store%20graph%0A%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv%2Cw)%3A%0A%20%20%20%20%20%20%20%20self.graph.append(%5Bu%2Cv%2Cw%5D)%0A%20%0A%20%20%20%20%23%20A%20utility%20function%20to%20find%20set%20of%20an%20element%20i%0A%20%20%20%20%23%20(uses%20path%20compression%20technique)%0A%20%20%20%20def%20find(self%2C%20parent%2C%20i)%3A%0A%20%20%20%20%20%20%20%20if%20parent%5Bi%5D%20%3D%3D%20i%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20i%0A%20%20%20%20%20%20%20%20return%20self.find(parent%2C%20parent%5Bi%5D)%0A%20%0A%20%20%20%20%23%20A%20function%20that%20does%20union%20of%20two%20sets%20of%20x%20and%20y%0A%20%20%20%20%23%20(uses%20union%20by%20rank)%0A%20%20%20%20def%20union(self%2C%20parent%2C%20rank%2C%20x%2C%20y)%3A%0A%20%20%20%20%20%20%20%20xroot%20%3D%20self.find(parent%2C%20x)%0A%20%20%20%20%20%20%20%20yroot%20%3D%20self.find(parent%2C%20y)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Attach%20smaller%20rank%20tree%20under%20root%20of%20high%20rank%20tree%0A%20%20%20%20%20%20%20%20%23%20(Union%20by%20Rank)%0A%20%20%20%20%20%20%20%20if%20rank%5Bxroot%5D%20%3C%20rank%5Byroot%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bxroot%5D%20%3D%20yroot%0A%20%20%20%20%20%20%20%20elif%20rank%5Bxroot%5D%20%3E%20rank%5Byroot%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Byroot%5D%20%3D%20xroot%0A%20%20%20%20%20%20%20%20%23If%20ranks%20are%20same%2C%20then%20make%20one%20as%20root%20and%20increment%0A%20%20%20%20%20%20%20%20%23%20its%20rank%20by%20one%0A%20%20%20%20%20%20%20%20else%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Byroot%5D%20%3D%20xroot%0A%20%20%20%20%20%20%20%20%20%20%20%20rank%5Bxroot%5D%20%2B%3D%201%0A%20%0A%20%20%20%20%23%20The%20main%20function%20to%20construct%20MST%20using%20Kruskal’s%20algorithm%0A%20%20%20%20def%20boruvkaMST(self)%3A%0A%20%20%20%20%20%20%20%20parent%20%3D%20%5B%5D%3B%20rank%20%3D%20%5B%5D%3B%20%0A%20%0A%20%20%20%20%20%20%20%20%23%20An%20array%20to%20store%20index%20of%20the%20cheapest%20edge%20of%0A%20%20%20%20%20%20%20%20%23%20subset.%20It%20store%20%5Bu%2Cv%2Cw%5D%20for%20each%20component%0A%20%20%20%20%20%20%20%20cheapest%20%3D%5B%5D%0A%20%0A%20%20%20%20%20%20%20%20%23%20Initially%20there%20are%20V%20different%20trees.%0A%20%20%20%20%20%20%20%20%23%20Finally%20there%20will%20be%20one%20tree%20that%20will%20be%20MST%0A%20%20%20%20%20%20%20%20numTrees%20%3D%20self.V%0A%20%20%20%20%20%20%20%20MSTweight%20%3D%200%0A%20%0A%20%20%20%20%20%20%20%20%23%20Create%20V%20subsets%20with%20single%20elements%0A%20%20%20%20%20%20%20%20for%20node%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20parent.append(node)%0A%20%20%20%20%20%20%20%20%20%20%20%20rank.append(0)%0A%20%20%20%20%20%20%20%20%20%20%20%20cheapest%20%3D%5B-1%5D%20*%20self.V%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Keep%20combining%20components%20(or%20sets)%20until%20all%0A%20%20%20%20%20%20%20%20%23%20compnentes%20are%20not%20combined%20into%20single%20MST%0A%20%0A%20%20%20%20%20%20%20%20while%20numTrees%20%3E%201%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Traverse%20through%20all%20edges%20and%20update%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20cheapest%20of%20every%20component%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%20in%20range(len(self.graph))%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Find%20components%20(or%20sets)%20of%20two%20corners%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20of%20current%20edge%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20u%2Cv%2Cw%20%3D%20%20self.graph%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20set1%20%3D%20self.find(parent%2C%20u)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20set2%20%3D%20self.find(parent%20%2Cv)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20two%20corners%20of%20current%20edge%20belong%20to%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20same%20set%2C%20ignore%20current%20edge.%20Else%20check%20if%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20current%20edge%20is%20closer%20to%20previous%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20cheapest%20edges%20of%20set1%20and%20set2%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20set1%20!%3D%20set2%3A%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20cheapest%5Bset1%5D%20%3D%3D%20-1%20or%20cheapest%5Bset1%5D%5B2%5D%20%3E%20w%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cheapest%5Bset1%5D%20%3D%20%5Bu%2Cv%2Cw%5D%20%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20cheapest%5Bset2%5D%20%3D%3D%20-1%20or%20cheapest%5Bset2%5D%5B2%5D%20%3E%20w%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cheapest%5Bset2%5D%20%3D%20%5Bu%2Cv%2Cw%5D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Consider%20the%20above%20picked%20cheapest%20edges%20and%20add%20them%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20to%20MST%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20node%20in%20range(self.V)%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23Check%20if%20cheapest%20for%20current%20set%20exists%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20cheapest%5Bnode%5D%20!%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20u%2Cv%2Cw%20%3D%20cheapest%5Bnode%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20set1%20%3D%20self.find(parent%2C%20u)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20set2%20%3D%20self.find(parent%20%2Cv)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20set1%20!%3D%20set2%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20MSTweight%20%2B%3D%20w%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.union(parent%2C%20rank%2C%20set1%2C%20set2)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20(%22Edge%20%25d-%25d%20with%20weight%20%25d%20included%20in%20MST%22%20%25%20(u%2Cv%2Cw))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20numTrees%20%3D%20numTrees%20-%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23reset%20cheapest%20array%0A%20%20%20%20%20%20%20%20%20%20%20%20cheapest%20%3D%5B-1%5D%20*%20self.V%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20print%20(%22Weight%20of%20MST%20is%20%25d%22%20%25%20MSTweight)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%0A%20%20%20%20%20%0Ag%20%3D%20Graph(4)%0Ag.addEdge(0%2C%201%2C%2010)%0Ag.addEdge(0%2C%202%2C%206)%0Ag.addEdge(0%2C%203%2C%205)%0Ag.addEdge(1%2C%203%2C%2015)%0Ag.addEdge(2%2C%203%2C%204)%0A%20%0Ag.boruvkaMST()” message=”” highlight=”” provider=”manual”/]

Output:

Edge 0-3 included in MST
Edge 0-1 included in MST
Edge 2-3 included in MST
Weight of MST is 19

Interesting Facts about Boruvka’s algorithm:
1) Time Complexity of Boruvka’s algorithm is O(E log V) which is same as Kruskal’s and Prim’s algorithms.

2) Boruvka’s algorithm is used as a step in a faster randomized algorithm that works in linear time O(E).

3) Boruvka’s algorithm is the oldest minimum spanning tree algorithm was discovered by Boruuvka in 1926, long before computers even existed. The algorithm was published as a method of constructing an efficient electricity network.

[ad type=”banner”]