Boruvka's Algorithm

Boruvka's Algorithm

This Algorithm's concept is simple and straightforward. We have noted that this was a greedy algorithm beforehand.

Greedy algorithms generate a globally "optimal" answer by combining smaller, locally optimum solutions for smaller subproblems. Following local optimums does not guarantee a globally optimal solution. Thus it usually converges with a good-enough solution.

Simply said, greedy algorithms select the best decision (out of all currently known options) at each stage of the problem, with the goal of arriving at the best overall solution when all of the smaller steps add up.

Now, we'll split down the Algorithm into a few steps:

• The input is a graph that is linked, weighted, and undirected.
• Initialize all vertices as separate components (or sets).
• Create an empty MST.
• If there are many components, perform the following for each one.

1. Find the nearest weight edge that connects this component to another.
2. If it hasn't already been done, add this nearest edge to MST.

• Back to MST

Let's look at the following graph and use Boruvka's approach to identify its Minimum spanning tree:

The graph above is an undirected, edge-weighted graph with six vertices. The above graph's minimum Spanning tree looks like this:
 

Explanation:

The figure above is the Minimum Spanning tree of Graph G, which connects all of the vertices. The resulting graph contains no loops or cycles. After experimenting with many cases, we choose the lowest edge from each vertex and link the two vertices. We avoid joining previously processed edges since it may generate a cycle. The Minimum Possible Weight of this MST is derived by combining the weights from the relevant edges: 

1 (Edge 1 to 2) + 4 (Edge 1 to 4) + 5 (Edge 2 to 3) + 3 (Edge 2 to 5) + 2 (Edge 5 to 6); 

hence, the Total Weight of MST is 15.

*Note

The maximum number of edges in a Minimum Spanning Tree is equal to the number of vertices minus one, (Tree = Number of Vertices – 1)

• The aim is to first segregate all nodes, then process each node individually by linking nodes from various components.
   
• We identify the edge with the least weight for each node and link them to make a component. We then go to the next vertex.
   
• We select the lowest or cheapest edge for each component, resulting in unconnected graph components. The graph is then combined in the manner described above. We discard any edges that include a loop or a cycle.
   
• After gathering all the separated components, we attempt to join them using the abovementioned techniques. Each iteration of this procedure decreases the number of nodes inside each linked component of the graph to at most half of the previous value. Hence the process is complete after logarithmically many repetitions.
   
• Finally, we add the weight of edges from the Minimum Spanning Tree.

Implementation 

Step 1: 

The graph represents a class with three fields: V, U, and Cost. V represents the source vertex, U represents the destination, and Cost is the weight between V and U. We use two arrays, Parent and Min. The Parent Array contains the node's parent, while Min records the pair's minimum outgoing edge (v,u). We set the parent value of the ith node to the same node.

Step 2:

We begin by limiting the number of Components to the number of vertices n. We set Min to -1 for each component to indicate that there is no cheapest edge. We do not process each node in our graph if its source and end vertex are part of the same component. Otherwise, we examine each vertex's root or parent node to see if it has a minimum weighted edge.

Step 3:

Then, we cycle through each component, and if a pair (u,v) has an edge, we combine them into a single component. Before merging, we check to see if the nodes are from the same component. This prevents us from merging two nodes into the same component, which might result in a loop or cycle. If the two components can be combined, we add their edge weight. These procedures are repeated for each component. This ensures that all edges are visited at least once, and we skip (log n) nodes on each iteration.

Let us now examine the above-mentioned implementation:

In Java
 

import java.util.*;
 
class edge_graph
{
    int v;
    int u;
    int cost;
    edge_graph(int v,int u,int cost)
    {
        this.v=v;
        this.u=u;
        this.cost=cost;
    }
}
 
public class MST_Boruvka
{
  static int parent[] = new int[7];
  static int Min[] = new int[7];
 
  public static void main(String args[])
  {
  // No. of vertices in the graph.
  int n=6;    
  edge_graph g[]=new edge_graph[10];
  
  // Creating the graph with the source, end, and cost of each edge
  g[1]=new edge_graph(1,2,1);
  g[2]=new edge_graph(1,4,4);
  g[3]=new edge_graph(2,4,7);
  g[4]=new edge_graph(2,5,3);
  g[5]=new edge_graph(2,6,6);
  g[6]=new edge_graph(3,2,5);
  g[7]=new edge_graph(3,6,9);
  g[8]=new edge_graph(6,5,2);
  g[9]=new edge_graph(5,4,8);
  
  // Initialises parent of all nodes.
  init(n);
  
  int edges = g.length-1;
  
  int components = n;
  int ans_MST=0;
  
  while(components>1)
  {
      // Initialise Min for each component as -1.
      for(int i=1;i<=n;i++)
      {
          Min[i]=-1;
      }
      for(int i=1;i<=edges;i++)
      {
          // If both source and end are from the same component, we don't process them.
          if(root(g[i].v)==root(g[i].u))
          continue;
          
          int r_v=root(g[i].v);
          if(Min[r_v]==-1 || g[i].cost < g[Min[r_v]].cost)
          Min[r_v]=i;
          
          int r_u=root(g[i].u);
          if(Min[r_u]==-1 || g[i].cost < g[Min[r_u]].cost)
          Min[r_u]=i;
          
      }
      
      for(int i=1;i<=n;i++)
      {
          if(Min[i]!=-1)
          {
              if(merge(g[Min[i]].v,g[Min[i]].u))
              {
                  ans_MST+=g[Min[i]].cost;
                  components--;
              }
          }
      }
  }
  
  System.out.println(" Overall Weight of The Minimum Spanning Tree is: "+ans_MST);
  
  }
 
  static int root(int v)
  {
      if(parent[v]==v)
      return v;
      
      return parent[v]=root(parent[v]);
  }
  
  static boolean merge(int v,int u)
  {
      v=root(v);
      u=root(u);
      if(v==u)
      return false;
      parent[v]=u;
      return true;
  }
 
  static void init(int n)
  {
      for(int i=1;i<=n;i++)
      {
          parent[i]=i;
      }
  }
  
}

You can also try this code with Online Java Compiler

Run Code

Output:

The overall Weight of The Minimum Spanning Tree is: 15

*Note

We use a Graph array of size ten since the total number of edges is 9 in the example above, and vertices are called from 1. The same holds true for the Parent and Min arrays; we use size 7 for six vertices.

We wrote the code for the same example given above. Let us now take a short look at the complexity.

Time Complexity

For N nodes in a network, we have E edges to verify the least weighted edge, and with each iteration, the number of nodes to be processed falls logarithmically. As a result, the overall Time complexity is O(E * log(N)).

Space Complexity

We need extra space in our graph of size equal to the entire number of vertices N to store each node's Parent and Min edge. As a result, the overall Space complexity is O(N).

Limitation of Boruvka’s Algorithm

In the above example, we can see that we employed a graph with separate weighted edges. This approach has a restriction in requiring the graph to be Edge-Weighted but with Distinct Weights. A consistent tie-breaking rule can be applied if no edges have separate weights. An optimization is to eliminate every edge in Graph G that connects two vertices in the same component.

Also Read - Kadanes Algorithm

• Prims and Kruskal Algorithm

Frequently Asked Questions

What is Boruvka's Algorithm?

Boruvka's Algorithm is a method for locating a minimal spanning tree — that is, a spanning tree in which the sum of edge weights is minimized. It was the first method created to locate MSTs (in 1926) and was used by Otakar Boruvka to identify the most effective route for an electrical grid.

What is MST(Minimum spanning Tree)?

An edge-weighted graph is one in which we assign weights or costs to each edge. An edge-weighted graph's Minimum spanning tree (MST) is a spanning tree whose weight (the sum of its edge weights) is not greater than the weight of any other spanning tree.

What is a Greedy Algorithm?

A greedy algorithm is a straightforward, intuitive technique used in optimization issues. The Algorithm chooses the best option at each stage in its quest to discover the best overall solution to the problem.

What is the Time Complexity of Boruvka Algorithms?

For N nodes in a network, we have E edges to verify the least weighted edge, and with each iteration, the number of nodes to be processed falls logarithmically. As a result, the overall complexity is O(E * log(N)).

What is the Space Complexity of Boruvka Algorithms?

We need extra space in our graph of size equal to the entire number of vertices N to store each node's Parent and Min edge. As a result, the overall complexity is O(N).

Read more, euclid gcd algorithm

Conclusion

In this article, we learned about Boruvka's Algorithm and dry run with various examples to have a clear idea.

After reading about Boruvka's Algorithm, are you not feeling excited to read/explore more articles on the topic of Ruby? Don't worry; Coding Ninjas has you covered. See Multithreading in Python, Descriptors in Python, and BorderLayout in Java.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! 

Do upvote our blogs if you find them helpful and engaging!