**I just announced the new *** Learn Spring * course, focused on the fundamentals of Spring 5 and Spring Boot 2:

*Learn Spring*course, focused on the fundamentals of Spring 5 and Spring Boot 2:

**>> CHECK OUT THE COURSE**

Last modified: March 24, 2020

In this tutorial, **we'll take a look at the Java implementation of Boruvka's algorithm for finding a Minimum Spanning Tree (MST) of an edge-weighted graph**.

It predates Prim's and Kruskal's algorithms, but still can be considered a cross between the two.

We'll jump right into the algorithm at hand. Let's look at a bit of history and then the algorithm itself.

A way to find an MST of a given graph was first formulated by Otakar Boruvka in 1926. This was way before computers even existed, and was in fact modeled to design an efficient electricity distribution system.

Georges Sollin rediscovered it in 1965 and used it in parallel computing.

The central idea of the algorithm is to start with a bunch of trees with each vertex representing an isolated tree. Then, we need to keep adding edges to reduce the number of isolated trees until we have a single connected tree.

Let's see this in steps with an example graph:

- Step 0: create a graph
- Step 1: start with a bunch of unconnected trees (number of trees = number of vertices)
- Step 2: while there are unconnected trees, for each unconnected tree:
- find its edge with lesser weight
- add this edge to connect another tree

Now let's see how we can implement this in Java.

To start with, **we need a data structure to store the parents and ranks of our vertices**.

Let's define a class *UnionFind* for this purpose, with two methods: *union*, and *find*:

public class UnionFind { private int[] parents; private int[] ranks; public UnionFind(int n) { parents = new int[n]; ranks = new int[n]; for (int i = 0; i < n; i++) { parents[i] = i; ranks[i] = 0; } } public int find(int u) { while (u != parents[u]) { u = parents[u]; } return u; } public void union(int u, int v) { int uParent = find(u); int vParent = find(v); if (uParent == vParent) { return; } if (ranks[uParent] < ranks[vParent]) { parents[uParent] = vParent; } else if (ranks[uParent] > ranks[vParent]) { parents[vParent] = uParent; } else { parents[vParent] = uParent; ranks[uParent]++; } } }

We may think of this class as a helper structure for maintaining relationships between our vertices and gradually building up our MST.

To find out **whether two vertices u and v belong to the same tree, we see if find(u) returns the same parent as find(v)**. The

Now we need a way to get a graph's vertices and edges from the user and map them to objects we can use in our algorithm at runtime.

Since we'll use JUnit to test out our algorithm, this part goes in a *@Before* method:

@Before public void setup() { graph = ValueGraphBuilder.undirected().build(); graph.putEdgeValue(0, 1, 8); graph.putEdgeValue(0, 2, 5); graph.putEdgeValue(1, 2, 9); graph.putEdgeValue(1, 3, 11); graph.putEdgeValue(2, 3, 15); graph.putEdgeValue(2, 4, 10); graph.putEdgeValue(3, 4, 7); }

Here, we've used Guava's *MutableValueGraph<Integer, Integer>* to store our graph. Then we used *ValueGraphBuilder* to construct an undirected weighted graph.

The method *putEdgeValue* takes three arguments, two *Integer*s for the vertices, and the third *Integer *for its weight, as specified by *MutableValueGraph*‘s generic type declaration.

As we can see, this is the same input as shown in our diagram from earlier.

Finally, we come to the crux of the matter, the implementation of the algorithm.

We'll do this in a class we'll call *BoruvkaMST*. First, let's declare a couple of instance variables:

public class BoruvkaMST { private static MutableValueGraph<Integer, Integer> mst = ValueGraphBuilder.undirected().build(); private static int totalWeight; }

As we can see, we are making use of *MutableValueGraph<Integer, Integer>* here to represent the MST.

Second, we'll define a constructor, where all the magic happens. It takes one argument – the *graph* we built earlier.

The first thing it does is to initialize a *UnionFind* of the input graph's vertices. Initially, all vertices are their own parents, each with a rank of 0:

public BoruvkaMST(MutableValueGraph<Integer, Integer> graph) { int size = graph.nodes().size(); UnionFind uf = new UnionFind(size);

Next, we'll create a loop that defines the number of iterations required to create the MST – at most log V times or until we have V-1 edges, where V is the number of vertices:

for (int t = 1; t < size && mst.edges().size() < size - 1; t = t + t) { EndpointPair<Integer>[] closestEdgeArray = new EndpointPair[size];

Here we also initialize an array of edges, *closestEdgeArray – *to store the closest, lesser-weighted edges.

After that, we'll define an inner *for* loop to iterate over all the edges of the graph to populate our *closestEdgeArray*.

If the parents of the two vertices are the same, it’s the same tree and we don’t add it to the array. Otherwise, we compare the current edge's weight to the weight of its parent vertices' edges. If it's lesser, then we add it to *closestEdgeArray:*

for (EndpointPair<Integer> edge : graph.edges()) { int u = edge.nodeU(); int v = edge.nodeV(); int uParent = uf.find(u); int vParent = uf.find(v); if (uParent == vParent) { continue; } int weight = graph.edgeValueOrDefault(u, v, 0); if (closestEdgeArray[uParent] == null) { closestEdgeArray[uParent] = edge; } if (closestEdgeArray[vParent] == null) { closestEdgeArray[vParent] = edge; } int uParentWeight = graph.edgeValueOrDefault(closestEdgeArray[uParent].nodeU(), closestEdgeArray[uParent].nodeV(), 0); int vParentWeight = graph.edgeValueOrDefault(closestEdgeArray[vParent].nodeU(), closestEdgeArray[vParent].nodeV(), 0); if (weight < uParentWeight) { closestEdgeArray[uParent] = edge; } if (weight < vParentWeight) { closestEdgeArray[vParent] = edge; } }

Then, we'll define a second inner loop to create a tree. We'll add edges from the above step to this tree without adding the same edge twice. Additionally, we'll perform a *union* on our *UnionFind* to derive and store parents and ranks of the newly created trees' vertices:

for (int i = 0; i < size; i++) { EndpointPair<Integer> edge = closestEdgeArray[i]; if (edge != null) { int u = edge.nodeU(); int v = edge.nodeV(); int weight = graph.edgeValueOrDefault(u, v, 0); if (uf.find(u) != uf.find(v)) { mst.putEdgeValue(u, v, weight); totalWeight += weight; uf.union(u, v); } } }

After repeating these steps at most log V times or until we have V-1 edges, the resulting tree is our MST.

Finally, let's see a simple JUnit to verify our implementation:

@Test public void givenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree() { BoruvkaMST boruvkaMST = new BoruvkaMST(graph); MutableValueGraph<Integer, Integer> mst = boruvkaMST.getMST(); assertEquals(30, boruvkaMST.getTotalWeight()); assertEquals(4, mst.getEdgeCount()); }

As we can see, we got the **MST with a weight of 30 and 4 edges, the same as the pictorial example**.

In this tutorial, we saw the Java implementation of the Boruvka Algorithm. **Its time complexity is O(E log V), where E is the number of edges and V is the number of vertices**.

As always, source code is available over on GitHub.

## Leave a Reply