Skip to main content

Boruvka’s Algorithm with Implementation in Java Vijay Sinha The Crazy Programmer

In this article, we will have a look at another interesting algorithm related to Graph Theory – Boruvka’s Algorithm. We will also look at a problem with respect to this algorithm, discuss our approach and analyze the complexities.

Boruvka’s Algorithm is mainly used to find or derive a Minimum Spanning Tree of an Edge-weighted Graph. Let us have a quick look at the concept of a Minimum Spanning Tree. A Minimum Spanning Tree or a MST is a subset of edges of a Weighted, Un-directed graph; such that it connects all the vertices together. The resultant subset of the graph must have no cycles or loops within it. Moreover, It should have minimum possible total weight of the edges connecting the tree.

Note: The Minimum Spanning Tree should connect all its vertices. A disconnected graph is not a MST.

Let us understand this with an example, consider this graph:

Boruvka's Algorithm

The above shown graph is an Edge-Weighted, undirected graph with 6 vertices. The minimum Spanning tree of the above graph looks like this:

Boruvka's_MST

Explanation:

The above image shows the Minimum Spanning tree of Graph G, as it connects all the vertices together. The resultant graph has no loops or cycles within it. After trying out various examples we select the smallest edge from each vertex and connect the two vertices together. We avoid connecting those edges which are already processed as it may form a cycle. The Minimum Possible Weight obtained from this MST adding all the weights from respective 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 ); so Total Weight of MST = 15.

Note: The Maximum Number of Edges present in a Minimum Spanning Tree = Number of Vertices – 1.

Boruvka’s Algorithm

Now let us see how Boruvka’s Algorithm is helpful in finding the MST of a graph.

  • The idea is to separate all nodes at first, then process each node one by one by connecting nodes together from different components.
  • For each node, we find the edge with least weight and connect them to form a component. Then we jump to the next vertex.
  • After this, for each component, we choose the smallest or cheapest edge so that we get disconnected components of graphs. Then we combine the graph using the above process. If any loop or cycle found we ignore those edges.
  • After getting all the disconnected components we try connecting them following the above steps. Each repetition of this process reduces the number of nodes, within each connected component of the graph, to at most half of this former value, so after logarithmically many repetitions the process finishes.
  • At the end, the weight of edges we add from the Minimum Spanning Tree.

Implementation in Java

Step 1:

We represent the Graph using a class with three fields: V, U, and Cost. V is the source vertex , U is the destination and Cost is the weight between V and U. We use two arrays Parent and Min. The Parent Array stores the parent of node and Min stores the Minimum outgoing edge for each pair (v,u). For ith node we initialize its parent value to the same node.

Step 2:

At first we set the number of Components to the number of vertices n. For each component we initialize Min as -1, indicating there is no cheapest edge. For each node in our graph if its source and end vertex are part of same component we do not process them. Otherwise, for each vertex we take their root or parent node and check if it is minimum weighted edge.

Step 3:

Then, we iterate through each component, if there is an each edge for pair (u,v) we merge them into a single component. Before merging we check if the nodes are from same component, on doing this we avoid merging two nodes into same component which might create a loop or cycle. If we are able to merge the two components we add their edge weight. We repeat these steps for each component. This makes sure all edges are visited at least once and on each iteration, we skip (log n) number of nodes.

Now let us look at the implementation of the above in Java code:

import java.util.*;

class Graph_Edge
{
    int v;
    int u;
    int cost;
    Graph_Edge(int v,int u,int cost)
    {
        this.v=v;
        this.u=u;
        this.cost=cost;
    }
}

public class Boruvka_MST
{
  static int parent[] = new int[7];
  static int Min[] = new int[7];

  public static void main(String args[]) 
  {
  // No. of vertices in graph.
  int n=6;     
  Graph_Edge g[]=new Graph_Edge[10];
  
  // Creating the graph with source, end and cost of each edge
  g[1]=new Graph_Edge(1,2,1);
  g[2]=new Graph_Edge(1,4,4);
  g[3]=new Graph_Edge(2,4,7);
  g[4]=new Graph_Edge(2,5,3);
  g[5]=new Graph_Edge(2,6,6);
  g[6]=new Graph_Edge(3,2,5);
  g[7]=new Graph_Edge(3,6,9);
  g[8]=new Graph_Edge(6,5,2);
  g[9]=new Graph_Edge(5,4,8);
  
  // Initializes parent of all nodes.
  init(n);
  
  int edges = g.length-1;
  
  int components = n;
  int ans_MST=0;
  
  while(components>1)
  {
      // Initialize 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 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("The Total Weight of 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;
      }
  }
  
}

Output:

The Total Weight of Minimum Spanning Tree is : 15

Note: We take Graph array of size 10 for total no. of edges are 9 as discussed in the example above and vertices are named from 1. The same is for Parent and Min array, we take size 7 for 6 vertices.

We have implemented the code for the same example as shown above. Now let us have a quick look at the complexities.

Time Complexity: For N nodes of graph, we have E edges to check the minimum weighted edge we have to iterate through all the edges and on each iteration the total nodes to be processed decreases logarithmically. So the overall complexity is O( E * log(N) ) .

Space Complexity: We require extra space to store the Parent and Min edge with respect to each node in our graph of size equal to the total number of vertices N. So the overall complexity is O(N).

Limitation Of Boruvka’s Algorithm

We can see in the above example that we used the graph with edges having distinct weight. This is a limitation for this algorithm which requires the graph to be Edge-Weighted but with Distinct Weights. If edges do not have distinct weights, then a consistent tie-breaking rule can be used. An optimization is to remove each edge in Graph G that is found to connect two vertices in the same component as each other.

So that’s it for the article you can try out this algorithm and dry run with various examples to have a clear idea. You can also execute this code to have a better understanding.

Feel free to leave your suggestions/doubts in the comment section below.

The post Boruvka’s Algorithm with Implementation in Java appeared first on The Crazy Programmer.



from The Crazy Programmer https://ift.tt/3csxfbM

Comments

Popular posts from this blog

Difference between Web Designer and Web Developer Neeraj Mishra The Crazy Programmer

Have you ever wondered about the distinctions between web developers’ and web designers’ duties and obligations? You’re not alone! Many people have trouble distinguishing between these two. Although they collaborate to publish new websites on the internet, web developers and web designers play very different roles. To put these job possibilities into perspective, consider the construction of a house. To create a vision for the house, including the visual components, the space planning and layout, the materials, and the overall appearance and sense of the space, you need an architect. That said, to translate an idea into a building, you need construction professionals to take those architectural drawings and put them into practice. Image Source In a similar vein, web development and design work together to create websites. Let’s examine the major responsibilities and distinctions between web developers and web designers. Let’s get going, shall we? What Does a Web Designer Do?

A guide to data integration tools

CData Software is a leader in data access and connectivity solutions. It specializes in the development of data drivers and data access technologies for real-time access to online or on-premise applications, databases and web APIs. The company is focused on bringing data connectivity capabilities natively into tools organizations already use. It also features ETL/ELT solutions, enterprise connectors, and data visualization. Matillion ’s data transformation software empowers customers to extract data from a wide number of sources, load it into their chosen cloud data warehouse (CDW) and transform that data from its siloed source state, into analytics-ready insights – prepared for advanced analytics, machine learning, and artificial intelligence use cases. Only Matillion is purpose-built for Snowflake, Amazon Redshift, Google BigQuery, and Microsoft Azure, enabling businesses to achieve new levels of simplicity, speed, scale, and savings. Trusted by companies of all sizes to meet

2022: The year of hybrid work

Remote work was once considered a luxury to many, but in 2020, it became a necessity for a large portion of the workforce, as the scary and unknown COVID-19 virus sickened and even took the lives of so many people around the world.  Some workers were able to thrive in a remote setting, while others felt isolated and struggled to keep up a balance between their work and home lives. Last year saw the availability of life-saving vaccines, so companies were able to start having the conversation about what to do next. Should they keep everyone remote? Should they go back to working in the office full time? Or should they do something in between? Enter hybrid work, which offers a mix of the two. A Fall 2021 study conducted by Google revealed that over 75% of survey respondents expect hybrid work to become a standard practice within their organization within the next three years.  Thus, two years after the world abruptly shifted to widespread adoption of remote work, we are declaring 20