# Boruvka's algorithm for minimum spanning trees

Boruvka's algorithm is a greedy algorithm for finding the minimum spanning tree of a graph. It was developed by Czech mathematician Otakar Boruvka in 1926.

The algorithm works by initially considering each vertex in the graph as a separate component, and then iteratively adding edges that connect the components together. At each iteration, the algorithm finds the minimum-weight edge that connects each component to another component, and adds these edges to the spanning tree.

This process is repeated until there is only one connected component remaining, which is the minimum spanning tree of the graph. The algorithm terminates when all the components are connected to each other.

Boruvka's algorithm has a time complexity of O(E log V), where E is the number of edges in the graph and V is the number of vertices. This makes it an efficient algorithm for finding the minimum spanning tree of a graph with a large number of vertices and edges. However, it is not as widely used as other algorithms such as Kruskal's or Prim's algorithms, as it requires more bookkeeping to keep track of the components and edges.

Here given code implementation process.

``````// Include header file
#include <iostream>

#include <vector>

using namespace std;
/*
C++ Program
Boruvka's algorithm for minimum spanning trees
*/
class Edge
{
public:
// Edge weight or cost
int weight;
int dest;
int src;
Edge *next;

Edge(int weight, int src, int dest)
{
this->weight = weight;
this->dest = dest;
this->src = src;
this->next = NULL;
}
};
class State
{
public: int parent;
int rank;
State(int parent, int rank)
{
this->parent = parent;
this->rank = rank;
}
};
class Graph
{
public: int vertices;
vector < vector < Edge *> > graphEdge;
Graph(int vertices)
{
this->vertices = vertices;

for (int i = 0; i < this->vertices; ++i)
{
this->graphEdge.push_back(vector < Edge *> ());
}
}
void addEdge(int src, int dest, int w)
{
if (dest < 0 || dest >= this->vertices ||
src < 0 || src >= this->vertices)
{
return;
}
this->graphEdge.at(src).push_back(new Edge(w, src, dest));
if (dest == src)
{
return;
}
this->graphEdge.at(dest).push_back(new Edge(w, dest, src));
}
void printGraph()
{
cout << "\n Graph Adjacency List ";
for (int i = 0; i < this->vertices; ++i)
{
cout << " \n [" << i << "] :";
// iterate edges of i node
for (int j = 0; j < this->graphEdge.at(i).size(); ++j)
{
cout << "  " << this->graphEdge.at(i).at(j)->dest;
}
}
}
int find(State **subsets, int i)
{
if (subsets[i]->parent != i)
{
subsets[i]->parent = this->find(subsets, subsets[i]->parent);
}
return subsets[i]->parent;
}
void findUnion(State **subsets, int x, int y)
{
int a = this->find(subsets, x);
int b = this->find(subsets, y);
if (subsets[a]->rank < subsets[b]->rank)
{
subsets[a]->parent = b;
}
else if (subsets[a]->rank > subsets[b]->rank)
{
subsets[b]->parent = a;
}
else
{
subsets[b]->parent = a;
subsets[a]->rank++;
}
}
void boruvkaMST()
{
// Contain weight sum in mst path
int result = 0;
int selector = this->vertices;
State **subsets = new State*[this->vertices];
Edge **cheapest = new Edge*[this->vertices];
for (int v = 0; v < this->vertices; ++v)
{
subsets[v] = new State(v, 0);
}
while (selector > 1)
{
for (int v = 0; v < this->vertices; ++v)
{
cheapest[v] = NULL;
}
for (int k = 0; k < this->vertices; k++)
{
for (int i = 0; i < this->graphEdge.at(k).size(); ++i)
{
int set1 = this->find(subsets,
this->graphEdge.at(k).at(i)->src);
int set2 = this->find(subsets,
this->graphEdge.at(k).at(i)->dest);
if (set1 != set2)
{
if (cheapest[k] == NULL)
{
cheapest[k] = this->graphEdge.at(k).at(i);
}
else if (cheapest[k]->weight >
this->graphEdge.at(k).at(i)->weight)
{
cheapest[k] = this->graphEdge.at(k).at(i);
}
}
}
}
for (int i = 0; i < this->vertices; i++)
{
if (cheapest[i] != NULL)
{
int set1 = this->find(subsets, cheapest[i]->src);
int set2 = this->find(subsets, cheapest[i]->dest);
if (set1 != set2)
{
// Reduce a edge
selector--;
this->findUnion(subsets, set1, set2);
// Display the edge connection
cout << "\n Include Edge ("
<< cheapest[i]->src
<< " - "
<< cheapest[i]->dest
<< ") weight "
<< cheapest[i]->weight;
result += cheapest[i]->weight;
}
}
}
}
cout << "\n Calculated total weight of MST is "
<< result << endl;
}
};
int main()
{
Graph *g = new Graph(10);
// Display graph element
g->printGraph();
// Find MST
g->boruvkaMST();
return 0;
}``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56``````
``````import java.util.ArrayList;
/*
Java Program
Boruvka's algorithm for minimum spanning trees
*/
class Edge
{
// Edge weight or cost
public int weight;
public int dest;
public int src;
public Edge next;
public Edge(int weight, int src, int dest)
{
this.weight = weight;
this.dest = dest;
this.src = src;
this.next = null;
}
}
class State
{
public int parent;
public int rank;
public State(int parent, int rank)
{
this.parent = parent;
this.rank = rank;
}
}
public class Graph
{
public int vertices;
public ArrayList < ArrayList < Edge >> graphEdge;
public Graph(int vertices)
{
this.vertices = vertices;
this.graphEdge = new ArrayList < ArrayList < Edge >> (vertices);
for (int i = 0; i < this.vertices; ++i)
{
this.graphEdge.add(new ArrayList < Edge > ());
}
}
public void addEdge(int src, int dest, int w)
{
if (dest < 0 || dest >= this.vertices || src < 0 || src >= this.vertices)
{
return;
}
if (dest == src)
{
return;
}
}
public void printGraph()
{
for (int i = 0; i < this.vertices; ++i)
{
System.out.print(" \n [" + i + "] :");
// iterate edges of i node
for (int j = 0; j < this.graphEdge.get(i).size(); ++j)
{
System.out.print("  " +
this.graphEdge.get(i).get(j).dest);
}
}
}
public int find(State[] subsets, int i)
{
if (subsets[i].parent != i)
{
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
void findUnion(State[] subsets, int x, int y)
{
int a = find(subsets, x);
int b = find(subsets, y);
if (subsets[a].rank < subsets[b].rank)
{
subsets[a].parent = b;
}
else if (subsets[a].rank > subsets[b].rank)
{
subsets[b].parent = a;
}
else
{
subsets[b].parent = a;
subsets[a].rank++;
}
}
public void boruvkaMST()
{
// Contain weight sum in mst path
int result = 0;
int selector = this.vertices;
State[] subsets = new State[this.vertices];
Edge[] cheapest = new Edge[this.vertices];
for (int v = 0; v < this.vertices; ++v)
{
subsets[v] = new State(v, 0);
}
while (selector > 1)
{
for (int v = 0; v < this.vertices; ++v)
{
cheapest[v] = null;
}
for (int k = 0; k < this.vertices; k++)
{
for (int i = 0; i < this.graphEdge.get(k).size(); ++i)
{
int set1 = find(subsets,
this.graphEdge.get(k).get(i).src);
int set2 = find(subsets,
this.graphEdge.get(k).get(i).dest);
if (set1 != set2)
{
if (cheapest[k] == null)
{
cheapest[k] = this.graphEdge.get(k).get(i);
}
else if (cheapest[k].weight >
this.graphEdge.get(k).get(i).weight)
{
cheapest[k] = this.graphEdge.get(k).get(i);
}
}
}
}
for (int i = 0; i < this.vertices; i++)
{
if (cheapest[i] != null)
{
int set1 = find(subsets, cheapest[i].src);
int set2 = find(subsets, cheapest[i].dest);
if (set1 != set2)
{
// Reduce a edge
selector--;
findUnion(subsets, set1, set2);
// Display the edge connection
System.out.print("\n Include Edge (" +
cheapest[i].src + " - " +
cheapest[i].dest + ") weight " +
cheapest[i].weight);
result += cheapest[i].weight;
}
}
}
}
System.out.println("\n Calculated total weight of MST is " +
result);
}
public static void main(String[] args)
{
Graph g = new Graph(10);
// Display graph element
g.printGraph();
// Find MST
g.boruvkaMST();
}
}``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Boruvka's algorithm for minimum spanning trees
*/
public class Edge
{
// Edge weight or cost
public int weight;
public int dest;
public int src;
public Edge next;
public Edge(int weight, int src, int dest)
{
this.weight = weight;
this.dest = dest;
this.src = src;
this.next = null;
}
}
public class State
{
public int parent;
public int rank;
public State(int parent, int rank)
{
this.parent = parent;
this.rank = rank;
}
}
public class Graph
{
public int vertices;
public List < List < Edge >> graphEdge;
public Graph(int vertices)
{
this.vertices = vertices;
this.graphEdge = new List < List < Edge >> (vertices);
for (int i = 0; i < this.vertices; ++i)
{
this.graphEdge.Add(new List < Edge > ());
}
}
public void addEdge(int src, int dest, int w)
{
if (dest < 0 || dest >= this.vertices || src < 0 || src >= this.vertices)
{
return;
}
if (dest == src)
{
return;
}
}
public void printGraph()
{
for (int i = 0; i < this.vertices; ++i)
{
Console.Write(" \n [" + i + "] :");
// iterate edges of i node
for (int j = 0; j < this.graphEdge[i].Count; ++j)
{
Console.Write("  " + this.graphEdge[i][j].dest);
}
}
}
public int find(State[] subsets, int i)
{
if (subsets[i].parent != i)
{
subsets[i].parent = this.find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
void findUnion(State[] subsets, int x, int y)
{
int a = this.find(subsets, x);
int b = this.find(subsets, y);
if (subsets[a].rank < subsets[b].rank)
{
subsets[a].parent = b;
}
else if (subsets[a].rank > subsets[b].rank)
{
subsets[b].parent = a;
}
else
{
subsets[b].parent = a;
subsets[a].rank++;
}
}
public void boruvkaMST()
{
// Contain weight sum in mst path
int result = 0;
int selector = this.vertices;
State[] subsets = new State[this.vertices];
Edge[] cheapest = new Edge[this.vertices];
for (int v = 0; v < this.vertices; ++v)
{
subsets[v] = new State(v, 0);
}
while (selector > 1)
{
for (int v = 0; v < this.vertices; ++v)
{
cheapest[v] = null;
}
for (int k = 0; k < this.vertices; k++)
{
for (int i = 0; i < this.graphEdge[k].Count; ++i)
{
int set1 = this.find(subsets, this.graphEdge[k][i].src);
int set2 = this.find(subsets, this.graphEdge[k][i].dest);
if (set1 != set2)
{
if (cheapest[k] == null)
{
cheapest[k] = this.graphEdge[k][i];
}
else if (cheapest[k].weight >
this.graphEdge[k][i].weight)
{
cheapest[k] = this.graphEdge[k][i];
}
}
}
}
for (int i = 0; i < this.vertices; i++)
{
if (cheapest[i] != null)
{
int set1 = this.find(subsets, cheapest[i].src);
int set2 = this.find(subsets, cheapest[i].dest);
if (set1 != set2)
{
// Reduce a edge
selector--;
this.findUnion(subsets, set1, set2);
// Display the edge connection
Console.Write("\n Include Edge (" +
cheapest[i].src + " - " +
cheapest[i].dest + ") weight " +
cheapest[i].weight);
result += cheapest[i].weight;
}
}
}
}
Console.WriteLine("\n Calculated total weight of MST is " + result);
}
public static void Main(String[] args)
{
Graph g = new Graph(10);
// Display graph element
g.printGraph();
// Find MST
g.boruvkaMST();
}
}``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56``````
``````<?php
/*
Php Program
Boruvka's algorithm for minimum spanning trees
*/
class Edge
{
// Edge weight or cost
public \$weight;
public \$dest;
public \$src;
public \$next;
public	function __construct(\$weight, \$src, \$dest)
{
\$this->weight = \$weight;
\$this->dest = \$dest;
\$this->src = \$src;
\$this->next = NULL;
}
}
class State
{
public \$parent;
public \$rank;
public	function __construct(\$parent, \$rank)
{
\$this->parent = \$parent;
\$this->rank = \$rank;
}
}
class Graph
{
public \$vertices;
public \$graphEdge;
public	function __construct(\$vertices)
{
\$this->vertices = \$vertices;
\$this->graphEdge = array();
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
\$this->graphEdge[] = array();
}
}
{
if (\$dest < 0 || \$dest >= \$this->vertices ||
\$src < 0 || \$src >= \$this->vertices)
{
return;
}
\$this->graphEdge[\$src][] = new Edge(\$w, \$src, \$dest);
if (\$dest == \$src)
{
return;
}
\$this->graphEdge[\$dest][] = new Edge(\$w, \$dest, \$src);
}
public	function printGraph()
{
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
echo(" \n [".\$i.
"] :");
// iterate edges of i node
for (\$j = 0; \$j < count(\$this->graphEdge[\$i]); ++\$j)
{
echo("  ".\$this->graphEdge[\$i][\$j]->dest);
}
}
}
public	function find(\$subsets, \$i)
{
if (\$subsets[\$i]->parent != \$i)
{
\$subsets[\$i]->parent = \$this->find(\$subsets, \$subsets[\$i]->parent);
}
return \$subsets[\$i]->parent;
}

function findUnion(\$subsets, \$x, \$y)
{
\$a = \$this->find(\$subsets, \$x);
\$b = \$this->find(\$subsets, \$y);
if (\$subsets[\$a]->rank < \$subsets[\$b]->rank)
{
\$subsets[\$a]->parent = \$b;
}
else if (\$subsets[\$a]->rank > \$subsets[\$b]->rank)
{
\$subsets[\$b]->parent = \$a;
}
else
{
\$subsets[\$b]->parent = \$a;
\$subsets[\$a]->rank++;
}
}
public	function boruvkaMST()
{
// Contain weight sum in mst path
\$result = 0;
\$selector = \$this->vertices;
\$subsets = array_fill(0, \$this->vertices, NULL);
\$cheapest = array_fill(0, \$this->vertices, NULL);
for (\$v = 0; \$v < \$this->vertices; ++\$v)
{
\$subsets[\$v] = new State(\$v, 0);
}
while (\$selector > 1)
{
for (\$v = 0; \$v < \$this->vertices; ++\$v)
{
\$cheapest[\$v] = NULL;
}
for (\$k = 0; \$k < \$this->vertices; \$k++)
{
for (\$i = 0; \$i < count(\$this->graphEdge[\$k]); ++\$i)
{
\$set1 = \$this->find(\$subsets, \$this->graphEdge[\$k][\$i]->src);
\$set2 = \$this->find(\$subsets, \$this->graphEdge[\$k][\$i]->dest);
if (\$set1 != \$set2)
{
if (\$cheapest[\$k] == NULL)
{
\$cheapest[\$k] = \$this->graphEdge[\$k][\$i];
}
else if (\$cheapest[\$k]->weight > \$this->graphEdge[\$k][\$i]->weight)
{
\$cheapest[\$k] = \$this->graphEdge[\$k][\$i];
}
}
}
}
for (\$i = 0; \$i < \$this->vertices; \$i++)
{
if (\$cheapest[\$i] != NULL)
{
\$set1 = \$this->find(\$subsets, \$cheapest[\$i]->src);
\$set2 = \$this->find(\$subsets, \$cheapest[\$i]->dest);
if (\$set1 != \$set2)
{
// Reduce a edge
\$selector--;
\$this->findUnion(\$subsets, \$set1, \$set2);
// Display the edge connection
echo("\n Include Edge (".\$cheapest[\$i]->src.
" - ".\$cheapest[\$i]->dest.
") weight ".\$cheapest[\$i]->weight);
\$result += \$cheapest[\$i]->weight;
}
}
}
}
echo("\n Calculated total weight of MST is ".\$result.
"\n");
}
}

function main()
{
\$g = new Graph(10);
// Display graph element
\$g->printGraph();
// Find MST
\$g->boruvkaMST();
}
main();``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56``````
``````/*
Node JS Program
Boruvka's algorithm for minimum spanning trees
*/
class Edge
{
constructor(weight, src, dest)
{
this.weight = weight;
this.dest = dest;
this.src = src;
this.next = null;
}
}
class State
{
constructor(parent, rank)
{
this.parent = parent;
this.rank = rank;
}
}
class Graph
{
constructor(vertices)
{
this.vertices = vertices;
this.graphEdge = [];
for (var i = 0; i < this.vertices; ++i)
{
this.graphEdge.push([]);
}
}
{
if (dest < 0 || dest >= this.vertices ||
src < 0 || src >= this.vertices)
{
return;
}
this.graphEdge[src].push(new Edge(w, src, dest));
if (dest == src)
{
return;
}
this.graphEdge[dest].push(new Edge(w, dest, src));
}
printGraph()
{
for (var i = 0; i < this.vertices; ++i)
{
process.stdout.write(" \n [" + i + "] :");
// iterate edges of i node
for (var j = 0; j < this.graphEdge[i].length; ++j)
{
process.stdout.write("  " + this.graphEdge[i][j].dest);
}
}
}
find(subsets, i)
{
if (subsets[i].parent != i)
{
subsets[i].parent = this.find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
findUnion(subsets, x, y)
{
var a = this.find(subsets, x);
var b = this.find(subsets, y);
if (subsets[a].rank < subsets[b].rank)
{
subsets[a].parent = b;
}
else if (subsets[a].rank > subsets[b].rank)
{
subsets[b].parent = a;
}
else
{
subsets[b].parent = a;
subsets[a].rank++;
}
}
boruvkaMST()
{
// Contain weight sum in mst path
var result = 0;
var selector = this.vertices;
var subsets = Array(this.vertices).fill(null);
var cheapest = Array(this.vertices).fill(null);
for (var v = 0; v < this.vertices; ++v)
{
subsets[v] = new State(v, 0);
}
while (selector > 1)
{
for (var v = 0; v < this.vertices; ++v)
{
cheapest[v] = null;
}
for (var k = 0; k < this.vertices; k++)
{
for (var i = 0; i < this.graphEdge[k].length; ++i)
{
var set1 = this.find(subsets,
this.graphEdge[k][i].src);
var set2 = this.find(subsets,
this.graphEdge[k][i].dest);
if (set1 != set2)
{
if (cheapest[k] == null)
{
cheapest[k] = this.graphEdge[k][i];
}
else if (cheapest[k].weight >
this.graphEdge[k][i].weight)
{
cheapest[k] = this.graphEdge[k][i];
}
}
}
}
for (var i = 0; i < this.vertices; i++)
{
if (cheapest[i] != null)
{
var set1 = this.find(subsets, cheapest[i].src);
var set2 = this.find(subsets, cheapest[i].dest);
if (set1 != set2)
{
// Reduce a edge
selector--;
this.findUnion(subsets, set1, set2);
// Display the edge connection
process.stdout.write("\n Include Edge (" +
cheapest[i].src + " - " +
cheapest[i].dest + ") weight " +
cheapest[i].weight);
result += cheapest[i].weight;
}
}
}
}
console.log("\n Calculated total weight of MST is " + result);
}
}

function main()
{
var g = new Graph(10);
// Display graph element
g.printGraph();
// Find MST
g.boruvkaMST();
}
main();``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56``````
``````#    Python 3 Program
#    Boruvka's algorithm for minimum spanning trees

class Edge :
#  Edge weight or cost
def __init__(self, weight, src, dest) :
self.weight = weight
self.dest = dest
self.src = src
self.next = None

class State :
def __init__(self, parent, rank) :
self.parent = parent
self.rank = rank

class Graph :
def __init__(self, vertices) :
self.vertices = vertices
self.graphEdge = []
i = 0
while (i < self.vertices) :
self.graphEdge.append([])
i += 1

def addEdge(self, src, dest, w) :
if (dest < 0 or dest >= self.vertices or src < 0 or src >= self.vertices) :
return

self.graphEdge[src].append(Edge(w, src, dest))
if (dest == src) :
return

self.graphEdge[dest].append(Edge(w, dest, src))

def printGraph(self) :
print("\n Graph Adjacency List ", end = "")
i = 0
while (i < self.vertices) :
print(" \n [", i ,"] :", end = "")
j = 0
#  iterate edges of i node
while (j < len(self.graphEdge[i])) :
print("  ", self.graphEdge[i][j].dest, end = "")
j += 1

i += 1

def find(self, subsets, i) :
if (subsets[i].parent != i) :
subsets[i].parent = self.find(subsets, subsets[i].parent)

return subsets[i].parent

def findUnion(self, subsets, x, y) :
a = self.find(subsets, x)
b = self.find(subsets, y)
if (subsets[a].rank < subsets[b].rank) :
subsets[a].parent = b
elif (subsets[a].rank > subsets[b].rank) :
subsets[b].parent = a
else :
subsets[b].parent = a
subsets[a].rank += 1

def boruvkaMST(self) :
#  Contain weight sum in mst path
result = 0
selector = self.vertices
subsets = [None] * (self.vertices)
cheapest = [None] * (self.vertices)
v = 0
while (v < self.vertices) :
subsets[v] = State(v, 0)
v += 1

while (selector > 1) :
v = 0
while (v < self.vertices) :
cheapest[v] = None
v += 1

k = 0
while (k < self.vertices) :
i = 0
while (i < len(self.graphEdge[k])) :
set1 = self.find(subsets, self.graphEdge[k][i].src)
set2 = self.find(subsets, self.graphEdge[k][i].dest)
if (set1 != set2) :
if (cheapest[k] == None) :
cheapest[k] = self.graphEdge[k][i]
elif (cheapest[k].weight > self.graphEdge[k][i].weight) :
cheapest[k] = self.graphEdge[k][i]

i += 1

k += 1

i = 0
while (i < self.vertices) :
if (cheapest[i] != None) :
set1 = self.find(subsets, cheapest[i].src)
set2 = self.find(subsets, cheapest[i].dest)
if (set1 != set2) :
#  Reduce a edge
selector -= 1
self.findUnion(subsets, set1, set2)
#  Display the edge connection
print("\n Include Edge (", cheapest[i].src ," - ", cheapest[i].dest ,") weight ", cheapest[i].weight, end = "")
result += cheapest[i].weight

i += 1

print("\n Calculated total weight of MST is ", result)

def main() :
g = Graph(10)
#  Display graph element
g.printGraph()
#  Find MST
g.boruvkaMST()

if __name__ == "__main__": main()``````

#### Output

`````` Graph Adjacency List
[ 0 ] :   1   7   8
[ 1 ] :   0   2   8
[ 2 ] :   1   3   6   9
[ 3 ] :   2   4   9
[ 4 ] :   3   5
[ 5 ] :   4   6   9
[ 6 ] :   2   5   7   8
[ 7 ] :   0   6
[ 8 ] :   0   1   6   9
[ 9 ] :   2   3   5   8
Include Edge ( 0  -  8 ) weight  4
Include Edge ( 1  -  8 ) weight  6
Include Edge ( 2  -  3 ) weight  8
Include Edge ( 3  -  9 ) weight  5
Include Edge ( 4  -  5 ) weight  15
Include Edge ( 5  -  9 ) weight  7
Include Edge ( 6  -  7 ) weight  2
Include Edge ( 8  -  9 ) weight  3
Include Edge ( 0  -  7 ) weight  6
Calculated total weight of MST is  56``````
``````#    Ruby Program
#    Boruvka's algorithm for minimum spanning trees
class Edge
# Define the accessor and reader of class Edge
attr_accessor :weight, :dest, :src, :next
#  Edge weight or cost
def initialize(weight, src, dest)
self.weight = weight
self.dest = dest
self.src = src
self.next = nil
end

end

class State
# Define the accessor and reader of class State
attr_accessor :parent, :rank
def initialize(parent, rank)
self.parent = parent
self.rank = rank
end

end

class Graph
# Define the accessor and reader of class Graph
attr_accessor :vertices, :graphEdge
def initialize(vertices)
self.vertices = vertices
self.graphEdge = []
i = 0
while (i < self.vertices)
self.graphEdge.push([])
i += 1
end

end

if (dest < 0 || dest >= self.vertices ||
src < 0 || src >= self.vertices)
return
end

self.graphEdge[src].push(Edge.new(w, src, dest))
if (dest == src)
return
end

self.graphEdge[dest].push(Edge.new(w, dest, src))
end

def printGraph()
i = 0
while (i < self.vertices)
print(" \n [", i ,"] :")
j = 0
#  iterate edges of i node
while (j < self.graphEdge[i].length)
print("  ", self.graphEdge[i][j].dest)
j += 1
end

i += 1
end

end

def find(subsets, i)
if (subsets[i].parent != i)
subsets[i].parent = self.find(subsets, subsets[i].parent)
end

return subsets[i].parent
end

def findUnion(subsets, x, y)
a = self.find(subsets, x)
b = self.find(subsets, y)
if (subsets[a].rank < subsets[b].rank)
subsets[a].parent = b
elsif (subsets[a].rank > subsets[b].rank)
subsets[b].parent = a
else

subsets[b].parent = a
subsets[a].rank += 1
end

end

def boruvkaMST()
#  Contain weight sum in mst path
result = 0
selector = self.vertices
subsets = Array.new(self.vertices) {nil}
cheapest = Array.new(self.vertices) {nil}
v = 0
while (v < self.vertices)
subsets[v] = State.new(v, 0)
v += 1
end

while (selector > 1)
v = 0
while (v < self.vertices)
cheapest[v] = nil
v += 1
end

k = 0
while (k < self.vertices)
i = 0
while (i < self.graphEdge[k].length)
set1 = self.find(subsets, self.graphEdge[k][i].src)
set2 = self.find(subsets, self.graphEdge[k][i].dest)
if (set1 != set2)
if (cheapest[k] == nil)
cheapest[k] = self.graphEdge[k][i]
elsif (cheapest[k].weight >
self.graphEdge[k][i].weight)
cheapest[k] = self.graphEdge[k][i]
end

end

i += 1
end

k += 1
end

i = 0
while (i < self.vertices)
if (cheapest[i] != nil)
set1 = self.find(subsets, cheapest[i].src)
set2 = self.find(subsets, cheapest[i].dest)
if (set1 != set2)
#  Reduce a edge
selector -= 1
self.findUnion(subsets, set1, set2)
#  Display the edge connection
print("\n Include Edge (",
cheapest[i].src ," - ",
cheapest[i].dest ,") weight ",
cheapest[i].weight)
result += cheapest[i].weight
end

end

i += 1
end

end

print("\n Calculated total weight of MST is ", result, "\n")
end

end

def main()
g = Graph.new(10)
#  Display graph element
g.printGraph()
#  Find MST
g.boruvkaMST()
end

main()``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56
``````
``````import scala.collection.mutable._;
/*
Scala Program
Boruvka's algorithm for minimum spanning trees
*/
class Edge(
// Edge weight or cost
var weight: Int,
var dest: Int,
var src: Int,
var next: Edge)
{
def this(weight: Int, src: Int, dest: Int)
{
this(weight, dest, src, null)
}
}
class State(var parent: Int,var rank: Int);
class Graph(var vertices: Int,
var graphEdge: ArrayBuffer[ArrayBuffer[Edge]])
{
def this(vertices: Int)
{
this(vertices, new ArrayBuffer[ArrayBuffer[Edge]](vertices))
var i: Int = 0;
while (i < this.vertices)
{
this.graphEdge += new ArrayBuffer[Edge]();
i += 1;
}

}
def addEdge(src: Int, dest: Int, w: Int): Unit = {
if (dest < 0 || dest >= this.vertices ||
src < 0 || src >= this.vertices)
{
return;
}
graphEdge(src) += new Edge(w, src, dest);
if (dest == src)
{
return;
}
graphEdge(dest) += new Edge(w, dest, src);
}
def printGraph(): Unit = {
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
while (j < this.graphEdge(i).size)
{
print("  " + this.graphEdge(i)(j).dest);
j += 1;
}
i += 1;
}
}
def find(subsets: Array[State], i: Int): Int = {
if (subsets(i).parent != i)
{
subsets(i).parent = find(subsets, subsets(i).parent);
}
return subsets(i).parent;
}
def findUnion(subsets: Array[State], x: Int, y: Int): Unit = {
var a: Int = find(subsets, x);
var b: Int = find(subsets, y);
if (subsets(a).rank < subsets(b).rank)
{
subsets(a).parent = b;
}
else if (subsets(a).rank > subsets(b).rank)
{
subsets(b).parent = a;
}
else
{
subsets(b).parent = a;
subsets(a).rank += 1;
}
}
def boruvkaMST(): Unit = {
// Contain weight sum in mst path
var result: Int = 0;
var selector: Int = this.vertices;
var subsets: Array[State] = Array.fill[State](this.vertices)(null);
var cheapest: Array[Edge] = Array.fill[Edge](this.vertices)(null);
var v: Int = 0;
while (v < this.vertices)
{
subsets(v) = new State(v, 0);
v += 1;
}
while (selector > 1)
{
var v: Int = 0;
while (v < this.vertices)
{
cheapest(v) = null;
v += 1;
}
var k: Int = 0;
while (k < this.vertices)
{
var i: Int = 0;
while (i < this.graphEdge(k).size)
{
var set1: Int = find(subsets, this.graphEdge(k)(i).src);
var set2: Int = find(subsets, this.graphEdge(k)(i).dest);
if (set1 != set2)
{
if (cheapest(k) == null)
{
cheapest(k) = this.graphEdge(k)(i);
}
else if (cheapest(k).weight >
this.graphEdge(k)(i).weight)
{
cheapest(k) = this.graphEdge(k)(i);
}
}
i += 1;
}
k += 1;
}
var i: Int = 0;
while (i < this.vertices)
{
if (cheapest(i) != null)
{
var set1: Int = find(subsets, cheapest(i).src);
var set2: Int = find(subsets, cheapest(i).dest);
if (set1 != set2)
{
// Reduce a edge
selector -= 1;
findUnion(subsets, set1, set2);
// Display the edge connection
print("\n Include Edge (" +
cheapest(i).src + " - " +
cheapest(i).dest + ") weight " +
cheapest(i).weight);
result += cheapest(i).weight;
}
}
i += 1;
}
}
println("\n Calculated total weight of MST is " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var g: Graph = new Graph(10);
// Display graph element
g.printGraph();
// Find MST
g.boruvkaMST();
}
}``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56``````
``````import Foundation;
/*
Swift 4 Program
Boruvka's algorithm for minimum spanning trees
*/
class Edge
{
// Edge weight or cost
var weight: Int;
var dest: Int;
var src: Int;
var next: Edge? ;
init(_ weight: Int, _ src: Int, _ dest: Int)
{
self.weight = weight;
self.dest = dest;
self.src = src;
self.next = nil;
}
}
class State
{
var parent: Int;
var rank: Int;
init(_ parent: Int, _ rank: Int)
{
self.parent = parent;
self.rank = rank;
}
}
class Graph
{
var vertices: Int;
var graphEdge: [[Edge?]];
init(_ vertices: Int)
{
self.vertices = vertices;
self.graphEdge = [[Edge?]]();
var i: Int = 0;
while (i < self.vertices)
{
self.graphEdge.append([Edge?]());
i += 1;
}
}
func addEdge(_ src: Int, _ dest: Int, _ w: Int)
{
if (dest < 0 || dest >= self.vertices ||
src < 0 || src >= self.vertices)
{
return;
}
self.graphEdge[src].append(Edge(w, src, dest));
if (dest == src)
{
return;
}
self.graphEdge[dest].append(Edge(w, dest, src));
}
func printGraph()
{
print("\n Graph Adjacency List ", terminator: "");
var i: Int = 0;
while (i < self.vertices)
{
print(" \n [", i ,"] :", terminator: "");
var j: Int = 0;
// iterate edges of i node
while (j < self.graphEdge[i].count)
{
print("  ", self.graphEdge[i][j]!.dest,
terminator: "");
j += 1;
}
i += 1;
}
}
func find(_ subsets: inout[State?], _ i: Int) -> Int
{
if (subsets[i]!.parent  != i)
{
subsets[i]!.parent = self.find(&subsets,
subsets[i]!.parent);
}
return subsets[i]!.parent;
}
func findUnion(_ subsets: inout[State?],
_ x: Int, _ y: Int)
{
let a: Int = self.find(&subsets, x);
let b: Int = self.find(&subsets, y);
if (subsets[a]!.rank < subsets[b]!.rank)
{
subsets[a]!.parent = b;
}
else if (subsets[a]!.rank > subsets[b]!.rank)
{
subsets[b]!.parent = a;
}
else
{
subsets[b]!.parent = a;
subsets[a]!.rank += 1;
}
}
func boruvkaMST()
{
// Contain weight sum in mst path
var result: Int = 0;
var selector: Int = self.vertices;
var subsets: [State?] = Array(repeating: nil,
count: self.vertices);
var cheapest: [Edge?] = Array(repeating: nil,
count: self.vertices);
var v: Int = 0;
while (v < self.vertices)
{
subsets[v] = State(v, 0);
v += 1;
}
while (selector > 1)
{
var v: Int = 0;
while (v < self.vertices)
{
cheapest[v] = nil;
v += 1;
}
var k: Int = 0;
while (k < self.vertices)
{
var i: Int = 0;
while (i < self.graphEdge[k].count)
{
let set1: Int = self.find(&subsets,
self.graphEdge[k][i]!.src);
let set2: Int = self.find(&subsets,
self.graphEdge[k][i]!.dest);
if (set1  != set2)
{
if (cheapest[k] == nil)
{
cheapest[k] = self.graphEdge[k][i];
}
else if (cheapest[k]!.weight >
self.graphEdge[k][i]!.weight)
{
cheapest[k] = self.graphEdge[k][i];
}
}
i += 1;
}
k += 1;
}
var i: Int = 0;
while (i < self.vertices)
{
if (cheapest[i]  != nil)
{
let set1: Int = self.find(&subsets,
cheapest[i]!.src);
let set2: Int = self.find(&subsets,
cheapest[i]!.dest);
if (set1  != set2)
{
// Reduce a edge
selector -= 1;
self.findUnion(&subsets, set1, set2);
// Display the edge connection
print("\n Include Edge (",
cheapest[i]!.src ," - ",
cheapest[i]!.dest ,") weight ",
cheapest[i]!.weight, terminator: "");
result += cheapest[i]!.weight;
}
}
i += 1;
}
}
print("\n Calculated total weight of MST is ",
result);
}
}
func main()
{
let g: Graph = Graph(10);
// Display graph element
g.printGraph();
// Find MST
g.boruvkaMST();
}
main();``````

#### Output

`````` Graph Adjacency List
[ 0 ] :   1   7   8
[ 1 ] :   0   2   8
[ 2 ] :   1   3   6   9
[ 3 ] :   2   4   9
[ 4 ] :   3   5
[ 5 ] :   4   6   9
[ 6 ] :   2   5   7   8
[ 7 ] :   0   6
[ 8 ] :   0   1   6   9
[ 9 ] :   2   3   5   8
Include Edge ( 0  -  8 ) weight  4
Include Edge ( 1  -  8 ) weight  6
Include Edge ( 2  -  3 ) weight  8
Include Edge ( 3  -  9 ) weight  5
Include Edge ( 4  -  5 ) weight  15
Include Edge ( 5  -  9 ) weight  7
Include Edge ( 6  -  7 ) weight  2
Include Edge ( 8  -  9 ) weight  3
Include Edge ( 0  -  7 ) weight  6
Calculated total weight of MST is  56``````
``````/*
Kotlin Program
Boruvka's algorithm for minimum spanning trees
*/
class Edge
{
// Edge weight or cost
var weight: Int;
var dest: Int;
var src: Int;
var next: Edge ? ;
constructor(weight: Int, src: Int, dest: Int)
{
this.weight = weight;
this.dest = dest;
this.src = src;
this.next = null;
}
}
class State
{
var parent: Int;
var rank: Int;
constructor(parent: Int, rank: Int)
{
this.parent = parent;
this.rank = rank;
}
}
class Graph
{
var vertices: Int;
var graphEdge: MutableList < MutableList < Edge >> ;
constructor(vertices: Int)
{
this.vertices = vertices;
this.graphEdge = mutableListOf<MutableList<Edge>>();
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
fun addEdge(src: Int, dest: Int, w: Int): Unit
{
if (dest < 0 || dest >= this.vertices ||
src < 0 || src >= this.vertices)
{
return;
}
if (dest == src)
{
return;
}
}
fun printGraph(): Unit
{
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
while (j < this.graphEdge[i].size)
{
print("  " + this.graphEdge[i][j].dest);
j += 1;
}
i += 1;
}
}
fun find(subsets: Array < State ? > , i : Int): Int
{
if (subsets[i]!!.parent != i)
{
subsets[i]!!.parent = this.find(subsets,
subsets[i]!!.parent);
}
return subsets[i]!!.parent;
}
fun findUnion(subsets: Array < State ? > , x : Int, y: Int): Unit
{
val a: Int = this.find(subsets, x);
val b: Int = this.find(subsets, y);
if (subsets[a]!!.rank < subsets[b]!!.rank)
{
subsets[a]!!.parent = b;
}
else if (subsets[a]!!.rank > subsets[b]!!.rank)
{
subsets[b]!!.parent = a;
}
else
{
subsets[b]!!.parent = a;
subsets[a]!!.rank += 1;
}
}
fun boruvkaMST(): Unit
{
// Contain weight sum in mst path
var result: Int = 0;
var selector: Int = this.vertices;
val subsets: Array < State ? > = Array(this.vertices)
{
null
};
val cheapest: Array < Edge ? > = Array(this.vertices)
{
null
};
var v: Int = 0;
while (v < this.vertices)
{
subsets[v] = State(v, 0);
v += 1;
}
while (selector > 1)
{
v = 0;
while (v < this.vertices)
{
cheapest[v] = null;
v += 1;
}
var k: Int = 0;
while (k < this.vertices)
{
var i: Int = 0;
while (i < this.graphEdge[k].size)
{
val set1: Int = this.find(subsets,
this.graphEdge[k][i].src);
val set2: Int = this.find(subsets,
this.graphEdge[k][i].dest);
if (set1 != set2)
{
if (cheapest[k] == null)
{
cheapest[k] = this.graphEdge[k][i];
}
else if (cheapest[k]!!.weight >
this.graphEdge[k][i].weight)
{
cheapest[k] = this.graphEdge[k][i];
}
}
i += 1;
}
k += 1;
}
var i: Int = 0;
while (i < this.vertices)
{
if (cheapest[i] != null)
{
val set1: Int = this.find(subsets,
cheapest[i]!!.src);
val set2: Int = this.find(subsets,
cheapest[i]!!.dest);
if (set1 != set2)
{
// Reduce a edge
selector -= 1;
this.findUnion(subsets, set1, set2);
// Display the edge connection
print("\n Include Edge (" +
cheapest[i]!!.src + " - " +
cheapest[i]!!.dest + ") weight " +
cheapest[i]!!.weight);
result += cheapest[i]!!.weight;
}
}
i += 1;
}
}
println("\n Calculated total weight of MST is " + result);
}
}
fun main(args: Array < String > ): Unit
{
val g: Graph = Graph(10);
// Display graph element
g.printGraph();
// Find MST
g.boruvkaMST();
}``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56``````
``````package main
import "fmt"
/*
Go Program
Boruvka's algorithm for minimum spanning trees
*/
type Edge struct {
// Edge weight or cost
weight int
dest int
src int
next * Edge
}
func getEdge(weight int, src int, dest int) * Edge {
var me *Edge = &Edge {}
me.weight = weight
me.dest = dest
me.src = src
me.next = nil
return me
}
type State struct {
parent int
rank int
}
func getState(parent int, rank int) * State {
var me *State = &State {}
me.parent = parent
me.rank = rank
return me
}
type Graph struct {
vertices int
graphEdge [][]*Edge
}
func getGraph(vertices int) * Graph {
var me *Graph = &Graph {}
me.vertices = vertices
me.graphEdge = make([][]*Edge,vertices)
for i := 0 ; i < me.vertices ; i++ {
me.graphEdge[i] = make([]*Edge,0 )
}
return me
}
func(this Graph) addEdge(src, dest, w int) {
if dest < 0 || dest >= this.vertices ||
src < 0 || src >= this.vertices {
return
}
this.graphEdge[src] = append(this.graphEdge[src],
getEdge(w, src, dest))
if dest == src {
return
}
this.graphEdge[dest] = append(this.graphEdge[dest],
getEdge(w, dest, src))
}
func(this Graph) printGraph() {
for i := 0 ; i < this.vertices ; i++ {
fmt.Print(" \n [", i, "] :")
// iterate edges of i node
for j := 0 ; j < len(this.graphEdge[i]) ; j++ {
fmt.Print("  ", this.graphEdge[i][j].dest)
}
}
}
func(this Graph) find(subsets[] *State, i int) int {
if subsets[i].parent != i {
subsets[i].parent = this.find(subsets,
subsets[i].parent)
}
return subsets[i].parent
}
func(this Graph) findUnion(subsets[] *State, x int, y int) {
var a int = this.find(subsets, x)
var b int = this.find(subsets, y)
if subsets[a].rank < subsets[b].rank {
subsets[a].parent = b
} else if subsets[a].rank > subsets[b].rank {
subsets[b].parent = a
} else {
subsets[b].parent = a
subsets[a].rank++
}
}
func(this Graph) boruvkaMST() {
// Contain weight sum in mst path
var result int = 0
var selector int = this.vertices
var subsets = make([] *State, this.vertices)
var cheapest = make([] *Edge, this.vertices)
for v := 0 ; v < this.vertices ; v++ {
subsets[v] = getState(v, 0)
}
for (selector > 1) {
for v := 0 ; v < this.vertices ; v++ {
cheapest[v] = nil
}
for k := 0 ; k < this.vertices ; k++ {
for i := 0 ; i < len(this.graphEdge[k]) ; i++ {
var set1 int = this.find(subsets,
this.graphEdge[k][i].src)
var set2 int = this.find(subsets,
this.graphEdge[k][i].dest)
if set1 != set2 {
if cheapest[k] == nil {
cheapest[k] = this.graphEdge[k][i]
} else if cheapest[k].weight >
this.graphEdge[k][i].weight {
cheapest[k] = this.graphEdge[k][i]
}
}
}
}
for i := 0 ; i < this.vertices ; i++ {
if cheapest[i] != nil {
var set1 int = this.find(subsets,
cheapest[i].src)
var set2 int = this.find(subsets,
cheapest[i].dest)
if set1 != set2 {
// Reduce a edge
selector--
this.findUnion(subsets, set1, set2)
// Display the edge connection
fmt.Print("\n Include Edge (",
cheapest[i].src, " - ", cheapest[i].dest, ") weight ", cheapest[i].weight)
result += cheapest[i].weight
}
}
}
}
fmt.Println("\n Calculated total weight of MST is ",
result)
}
func main() {
var g * Graph = getGraph(10)
// Display graph element
g.printGraph()
// Find MST
g.boruvkaMST()
}``````

#### Output

`````` Graph Adjacency List
[0] :  1  7  8
[1] :  0  2  8
[2] :  1  3  6  9
[3] :  2  4  9
[4] :  3  5
[5] :  4  6  9
[6] :  2  5  7  8
[7] :  0  6
[8] :  0  1  6  9
[9] :  2  3  5  8
Include Edge (0 - 8) weight 4
Include Edge (1 - 8) weight 6
Include Edge (2 - 3) weight 8
Include Edge (3 - 9) weight 5
Include Edge (4 - 5) weight 15
Include Edge (5 - 9) weight 7
Include Edge (6 - 7) weight 2
Include Edge (8 - 9) weight 3
Include Edge (0 - 7) weight 6
Calculated total weight of MST is 56``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.