Skip to main content

Boruvka's algorithm for minimum spanning trees

Minimum spanning tree example

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
Last updated on by Kalkicode




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.

New Comment