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;
}
// add node edge
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;
// Add weight
result += cheapest[i]->weight;
}
}
}
}
cout << "\n Calculated total weight of MST is "
<< result << endl;
}
};
int main()
{
Graph *g = new Graph(10);
g->addEdge(0, 1, 7);
g->addEdge(0, 7, 6);
g->addEdge(0, 8, 4);
g->addEdge(1, 2, 9);
g->addEdge(1, 8, 6);
g->addEdge(2, 3, 8);
g->addEdge(2, 6, 12);
g->addEdge(2, 9, 14);
g->addEdge(3, 4, 16);
g->addEdge(3, 9, 5);
g->addEdge(4, 5, 15);
g->addEdge(5, 6, 8);
g->addEdge(5, 9, 7);
g->addEdge(6, 7, 2);
g->addEdge(6, 8, 10);
g->addEdge(8, 9, 3);
// 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;
}
// add node edge
graphEdge.get(src).add(new Edge(w, src, dest));
if (dest == src)
{
return;
}
graphEdge.get(dest).add(new Edge(w, dest, src));
}
public void printGraph()
{
System.out.print("\n Graph Adjacency List ");
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);
// Add 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);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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;
}
// add node edge
this.graphEdge[src].Add(new Edge(w, src, dest));
if (dest == src)
{
return;
}
this.graphEdge[dest].Add(new Edge(w, dest, src));
}
public void printGraph()
{
Console.Write("\n Graph Adjacency List ");
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);
// Add 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);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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();
}
}
public function addEdge($src, $dest, $w)
{
if ($dest < 0 || $dest >= $this->vertices ||
$src < 0 || $src >= $this->vertices)
{
return;
}
// add node edge
$this->graphEdge[$src][] = new Edge($w, $src, $dest);
if ($dest == $src)
{
return;
}
$this->graphEdge[$dest][] = new Edge($w, $dest, $src);
}
public function printGraph()
{
echo("\n Graph Adjacency List ");
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);
// Add weight
$result += $cheapest[$i]->weight;
}
}
}
}
echo("\n Calculated total weight of MST is ".$result.
"\n");
}
}
function main()
{
$g = new Graph(10);
$g->addEdge(0, 1, 7);
$g->addEdge(0, 7, 6);
$g->addEdge(0, 8, 4);
$g->addEdge(1, 2, 9);
$g->addEdge(1, 8, 6);
$g->addEdge(2, 3, 8);
$g->addEdge(2, 6, 12);
$g->addEdge(2, 9, 14);
$g->addEdge(3, 4, 16);
$g->addEdge(3, 9, 5);
$g->addEdge(4, 5, 15);
$g->addEdge(5, 6, 8);
$g->addEdge(5, 9, 7);
$g->addEdge(6, 7, 2);
$g->addEdge(6, 8, 10);
$g->addEdge(8, 9, 3);
// 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([]);
}
}
addEdge(src, dest, w)
{
if (dest < 0 || dest >= this.vertices ||
src < 0 || src >= this.vertices)
{
return;
}
// add node edge
this.graphEdge[src].push(new Edge(w, src, dest));
if (dest == src)
{
return;
}
this.graphEdge[dest].push(new Edge(w, dest, src));
}
printGraph()
{
process.stdout.write("\n Graph Adjacency List ");
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);
// Add weight
result += cheapest[i].weight;
}
}
}
}
console.log("\n Calculated total weight of MST is " + result);
}
}
function main()
{
var g = new Graph(10);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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
# add node edge
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 = "")
# Add weight
result += cheapest[i].weight
i += 1
print("\n Calculated total weight of MST is ", result)
def main() :
g = Graph(10)
g.addEdge(0, 1, 7)
g.addEdge(0, 7, 6)
g.addEdge(0, 8, 4)
g.addEdge(1, 2, 9)
g.addEdge(1, 8, 6)
g.addEdge(2, 3, 8)
g.addEdge(2, 6, 12)
g.addEdge(2, 9, 14)
g.addEdge(3, 4, 16)
g.addEdge(3, 9, 5)
g.addEdge(4, 5, 15)
g.addEdge(5, 6, 8)
g.addEdge(5, 9, 7)
g.addEdge(6, 7, 2)
g.addEdge(6, 8, 10)
g.addEdge(8, 9, 3)
# 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_reader :weight, :dest, :src, :next
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_reader :parent, :rank
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_reader :vertices, :graphEdge
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
def addEdge(src, dest, w)
if (dest < 0 || dest >= self.vertices ||
src < 0 || src >= self.vertices)
return
end
# add node edge
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()
print("\n Graph Adjacency List ")
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)
# Add 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)
g.addEdge(0, 1, 7)
g.addEdge(0, 7, 6)
g.addEdge(0, 8, 4)
g.addEdge(1, 2, 9)
g.addEdge(1, 8, 6)
g.addEdge(2, 3, 8)
g.addEdge(2, 6, 12)
g.addEdge(2, 9, 14)
g.addEdge(3, 4, 16)
g.addEdge(3, 9, 5)
g.addEdge(4, 5, 15)
g.addEdge(5, 6, 8)
g.addEdge(5, 9, 7)
g.addEdge(6, 7, 2)
g.addEdge(6, 8, 10)
g.addEdge(8, 9, 3)
# 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;
}
// add node edge
graphEdge(src) += new Edge(w, src, dest);
if (dest == src)
{
return;
}
graphEdge(dest) += new Edge(w, dest, src);
}
def printGraph(): Unit = {
print("\n Graph Adjacency List ");
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);
// Add 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);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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;
}
// add node edge
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: "");
// Add weight
result += cheapest[i]!.weight;
}
}
i += 1;
}
}
print("\n Calculated total weight of MST is ",
result);
}
}
func main()
{
let g: Graph = Graph(10);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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)
{
this.graphEdge.add(mutableListOf < Edge > ());
i += 1;
}
}
fun addEdge(src: Int, dest: Int, w: Int): Unit
{
if (dest < 0 || dest >= this.vertices ||
src < 0 || src >= this.vertices)
{
return;
}
// add node edge
this.graphEdge[src].add(Edge(w, src, dest));
if (dest == src)
{
return;
}
this.graphEdge[dest].add(Edge(w, dest, src));
}
fun printGraph(): Unit
{
print("\n Graph Adjacency List ");
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);
// Add 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);
g.addEdge(0, 1, 7);
g.addEdge(0, 7, 6);
g.addEdge(0, 8, 4);
g.addEdge(1, 2, 9);
g.addEdge(1, 8, 6);
g.addEdge(2, 3, 8);
g.addEdge(2, 6, 12);
g.addEdge(2, 9, 14);
g.addEdge(3, 4, 16);
g.addEdge(3, 9, 5);
g.addEdge(4, 5, 15);
g.addEdge(5, 6, 8);
g.addEdge(5, 9, 7);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 10);
g.addEdge(8, 9, 3);
// 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
}
// add node edge
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() {
fmt.Print("\n Graph Adjacency List ")
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)
// Add weight
result += cheapest[i].weight
}
}
}
}
fmt.Println("\n Calculated total weight of MST is ",
result)
}
func main() {
var g * Graph = getGraph(10)
g.addEdge(0, 1, 7)
g.addEdge(0, 7, 6)
g.addEdge(0, 8, 4)
g.addEdge(1, 2, 9)
g.addEdge(1, 8, 6)
g.addEdge(2, 3, 8)
g.addEdge(2, 6, 12)
g.addEdge(2, 9, 14)
g.addEdge(3, 4, 16)
g.addEdge(3, 9, 5)
g.addEdge(4, 5, 15)
g.addEdge(5, 6, 8)
g.addEdge(5, 9, 7)
g.addEdge(6, 7, 2)
g.addEdge(6, 8, 10)
g.addEdge(8, 9, 3)
// 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
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.
New Comment