Boruvka’s Algorithm

Here I will be discussing Boruvka’s minimum spanning tree Algorithm. You might know the more known spanning tree algorithms like Kruskal’s and Prim’s spanning tree algorithms. Like these 2 algo’s Boruvka’s is also a greedy algorithm.

First of all, what is a greedy algorithm? A greedy algorithm is an approach to a problem where we go one step at a time selecting the best possible choice among the options available to us at that juncture. Therefore the best place to use a greedy algorithm is places where choosing the option with immediate benefit during a process also provides the best outcome at the end of the process.

Greedy algorithm is used in many different algorithms like fractional Knapsack, Kruskal’s Spanning tree, Egyptian Fraction problem, etc.

The one we are discussing here is an implementation of the greedy algorithm in graphs known as you guessed it “Boruvkas’s Algorithm”.

What is Boruvka’s algorithm?

The thought process behind Boruvka’s algorithm is that we need to connect every vertex of the graph while also making sure that we achieve it by connecting each of them using the least weighted edge. We make a minimum spanning tree.

Approach for Boruvka’s Algo

We take input of the vertices which makes an undirected graph. We then initialize the minimum spanning tree (MST) as empty.

Step 2 — This is where we start the real deal the next step is repeated for each component until we achieve the target of joining all vertices and making them a set of one single component. Also, after every repetition, the number of components we are left with is halved.

So, for each component, we search the least weight edge that connects it to another component. Now, if this component is not added already to the MST we add it to the MST.

When we are able to arrive at the junction when we are only left with one component which includes every single vertice of the graph, we return the graph.

This is the point where we are done and have achieved our goal

Time Complexity (T)

Considering that the graph has V number of vertices and E number of edges in it.

The loop will be halving the number of components every time it runs and since we have a V number of components at the start, the run time for the loop part of the algorithm is Log(V) time. Now, during every iteration of the loop we go through every edge in order to select the best choice hence adding the time to achieve it we get the run time or the time complexity for our algorithm as O(E*Log(V)).