Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Boruvka's Algorithm is another intriguing algorithm linked to Graph Theory that we will look at in this article. In addition, we will look at an issue related to this technique, outline our approach, and examine the difficulties.

Borvka's algorithm approach is a greedy algorithm for locating the Minimum Spanning tree in a graph or the Minimum spanning forest in the case of an unconnected network.

Its most well-known use is for determining the minimal spanning tree in a graph.

About Tree and Minimum Spanning Tree

There's a lot to say about Trees, subgraphs, and spanning trees, but here's a short analysis.

Tree

A tree is an undirected network in which each node is connected by exactly one path, no more, no fewer.

Subgraphs

A subgraph of graph A is a graph made up of a subset of the nodes and edges of graph A.

Minimum Spanning Tree

A minimal spanning tree is a spanning tree in which the total of all edge weights is as little as feasible. There should be no cycles because it is a tree (and the edge weight total should be small).

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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.

Find the nearest weight edge that connects this component to another.

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.

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;
}
}
}

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.

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