Borůvka algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a connected, undirected graph with weighted edges. It was first published by Czech mathematician Otakar Borůvka in 1926, making it the oldest known algorithm for finding minimum spanning trees.
- Description
The algorithm begins with a forest of single-vertex trees (each vertex of the graph as a separate tree) and iteratively merges these trees until a single tree remains, which is the minimum spanning tree of the graph.
The algorithm proceeds in a series of stages:
- Initially, each vertex is considered as a separate tree in the forest.
- For each tree in the current forest, find the minimum-weight edge that connects this tree to any other tree in the forest.
- Add all such minimum-weight edges to the MST being constructed.
- Each such edge merges two trees in the forest.
- If there is more than one tree left, repeat steps 2-4.
At each stage, the number of trees in the forest is at least halved, which ensures that the algorithm terminates after at most log(V) stages, where V is the number of vertices in the graph.
- Time complexity
Borůvka's algorithm has a time complexity of , where is the number of edges and is the number of vertices. This makes it asymptotically equivalent to other minimum spanning tree algorithms like Kruskal's algorithm and Prim's algorithm.
- Applications
Borůvka's algorithm is used in various applications, including:
- Network design
- Cluster analysis
- Approximation algorithms for NP-hard problems like the Traveling salesman problem
- Comparison to other MST algorithms
While Borůvka's algorithm has the same asymptotic time complexity as Kruskal's and Prim's algorithms, it has certain advantages:
- It can be parallelized more effectively than the other algorithms.
- It does not require a priority queue, making the implementation simpler in some contexts.
- It was historically significant as the first algorithm for the MST problem.
- History
Borůvka originally developed this algorithm to find an efficient electricity network for Moravia, a region in the Czech Republic. Despite being the first MST algorithm, it did not receive as much attention as the later algorithms by Kruskal and Prim until relatively recently when its parallelization advantages were recognized.
C++
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
struct Edge {
uint32_t u;
uint32_t v;
double weight;
};
class Graph {
public:
Graph(const uint32_t& a_vertex_count) {
vertex_count = a_vertex_count;
}
void add_edge(const Edge& edge) {
edges.emplace_back(edge);
}
// Return the minimum spanning tree by using Boruvka's algorithm
void borůvka_minimum_spanning_tree() {
std::vector<uint32_t> parent(vertex_count);
std::iota(parent.begin(), parent.end(), 0);
std::vector<uint32_t> rank(vertex_count, 0);
// Store the indexes of the cheapest edge for each tree
std::vector<Edge> cheapest(vertex_count, Edge(-1, -1, -1.0));
// Initially there are 'vertex_count' different trees
uint32_t tree_count = vertex_count;
uint32_t minimum_spanning_tree_weight = 0;
// Combine trees until all trees are combined into a single minimum spanning tree
while ( tree_count > 1 ) {
// Traverse through all edges and update cheapest edge for every tree
for ( const Edge& edge : edges ) {
const uint32_t u = edge.u;
const uint32_t v = edge.v;
const double weight = edge.weight;
const uint32_t index1 = find(parent, u);
const uint32_t index2 = find(parent, v);
// If the two vertices of the current edge belong to different trees,
// check whether the current edge is cheaper than previous cheapest edges
if ( index1 != index2 ) {
if ( cheapest[index1].weight == -1.0 || cheapest[index1].weight > weight ) {
cheapest[index1] = Edge(u, v, weight);
}
if ( cheapest[index2].weight == -1.0 || cheapest[index2].weight > weight ) {
cheapest[index2] = Edge(u, v, weight);
}
}
}
// Add the cheapest edges to the minimum spanning tree
for ( uint32_t vertex = 0; vertex < vertex_count; ++vertex ) {
// Check whether the cheapest edge for current vertex exists
if ( cheapest[vertex].weight != -1.0 ) {
const uint32_t u = cheapest[vertex].u;
const uint32_t v = cheapest[vertex].v;
const double weight = cheapest[vertex].weight;
const uint32_t index1 = find(parent, u);
const uint32_t index2 = find(parent, v);
if ( index1 != index2 ) {
minimum_spanning_tree_weight += weight;
unionSet(parent, rank, index1, index2);
std::cout << "Edge " << u << "--" << v << " with weight " << weight
<< " is included in the minimum spanning tree" << std::endl;
tree_count -= 1;
}
}
}
}
std::cout << "\n" << "Weight of minimum spanning tree is " << minimum_spanning_tree_weight << std::endl;
}
private:
// Return the index of the tree containing 'vertex', using a path compression technique
uint32_t find(std::vector<uint32_t>& parent, const uint32_t& vertex) {
if ( parent[vertex] != vertex ) {
parent[vertex] = find(parent, parent[vertex]);
}
return parent[vertex];
}
// Form the union by rank of the two trees indexed by u and v
void unionSet(std::vector<uint32_t>& parent, std::vector<uint32_t>& rank, const uint32_t& u, const uint32_t& v) {
const uint32_t uRoot = find(parent, u);
const uint32_t vRoot = find(parent, v);
// Attach the smaller rank tree under root of the high rank tree
switch ( ( rank[uRoot] < rank[vRoot] ) ? -1 : ( rank[uRoot] > rank[vRoot] ) ) {
case -1 : parent[uRoot] = vRoot; break;
case +1 : parent[vRoot] = uRoot; break;
// If ranks are the same, make one the root and increment its rank
case 0 : { parent[vRoot] = uRoot; rank[uRoot] += 1; break; }
}
}
std::vector<Edge> edges;
uint32_t vertex_count;
};
int main() {
Graph graph(4);
graph.add_edge(Edge(0, 1, 10.0));
graph.add_edge(Edge(0, 2, 6.0));
graph.add_edge(Edge(0, 3, 5.0));
graph.add_edge(Edge(1, 3, 15.0));
graph.add_edge(Edge(2, 3, 4.0));
graph.borůvka_minimum_spanning_tree();
}
- Output:
Edge 0--3 with weight 5 is included in the minimum spanning tree Edge 0--1 with weight 10 is included in the minimum spanning tree Edge 2--3 with weight 4 is included in the minimum spanning tree Weight of minimum spanning tree is 19
FreeBASIC
' Structure for edges
Type Edge
u As Integer
v As Integer
w As Integer
End Type
' Structure to represent a graph
Type Graph
v As Integer ' Number of vertices
edges(Any) As Edge ' List of edges [u, v, w]
End Type
Function GraphNew(vertices As Integer) As Graph
Dim As Graph g
g.v = vertices
Redim g.edges(-1)
Return g
End Function
' Function to add an edge to the graph
Sub AddEdge(Byref g As Graph, u As Integer, v As Integer, w As Integer)
Dim As Integer n = Ubound(g.edges) + 1
Redim Preserve g.edges(n)
g.edges(n).u = u
g.edges(n).v = v
g.edges(n).w = w
End Sub
' A utility function to find the set of an element i
' (uses path compression technique)
Function Find(parent() As Integer, i As Integer) As Integer
If parent(i) <> i Then parent(i) = Find(parent(), parent(i))
Return parent(i)
End Function
' A function that performs union of two sets x and y
' (uses union by rank)
Sub UnionSet(parent() As Integer, rank() As Integer, x As Integer, y As Integer)
Dim As Integer x_root = Find(parent(), x)
Dim As Integer y_root = Find(parent(), y)
If x_root = y_root Then Return
' Attach smaller rank tree under root of high rank tree
If rank(x_root) < rank(y_root) Then
parent(x_root) = y_root
Elseif rank(x_root) > rank(y_root) Then
parent(y_root) = x_root
Else
' If ranks are the same, make one as root and increment its rank
parent(y_root) = x_root
rank(x_root) += 1
End If
End Sub
' The main function to construct MST using Boruvka's algorithm
Sub BoruvkaMST(g As Graph)
Dim As Integer i, u, v, w, set1, set2
v = g.v
Dim As Integer parent(v - 1)
Dim As Integer rank(v - 1)
' An array to store the index of the cheapest edge of each subset
' It stores [u, v, w] for each component
Dim As Integer cheapest(v - 1, 2) ' [u, v, w]
' Initially there are V different trees
' Finally there will be one tree that will be the MST
Dim As Integer num_trees = v
Dim As Integer mst_weight = 0
For i = 0 To v - 1
parent(i) = i
rank(i) = 0
Next
' Keep combining components (or sets) until all
' components are combined into a single MST
While num_trees > 1
' Initialize the cheapest array
For i = 0 To v - 1
cheapest(i, 0) = -1
cheapest(i, 1) = -1
cheapest(i, 2) = -1
Next
' Find the cheapest edge for each component
For i = 0 To Ubound(g.edges)
u = g.edges(i).u
v = g.edges(i).v
w = g.edges(i).w
set1 = Find(parent(), u)
set2 = Find(parent(), v)
' If two corners of current edge belong to different sets,
' check if current edge is cheaper than previous cheapest edges
If set1 <> set2 Then
If cheapest(set1, 2) = -1 Orelse w < cheapest(set1, 2) Then
cheapest(set1, 0) = u
cheapest(set1, 1) = v
cheapest(set1, 2) = w
End If
If cheapest(set2, 2) = -1 Orelse w < cheapest(set2, 2) Then
cheapest(set2, 0) = u
cheapest(set2, 1) = v
cheapest(set2, 2) = w
End If
End If
Next
' Consider the picked cheapest edges and add them to the MST
For i = 0 To v - 1
' Check if cheapest edge for current set exists
If cheapest(i, 2) <> -1 Then
u = cheapest(i, 0)
v = cheapest(i, 1)
w = cheapest(i, 2)
set1 = Find(parent(), u)
set2 = Find(parent(), v)
If set1 <> set2 Then
mst_weight += w
UnionSet(parent(), rank(), set1, set2)
Print Using "Edge #_-# With weight & included in MST"; u; v; w
num_trees -= 1
End If
End If
Next
Wend
Print !"\nWeight of MST is "; mst_weight
End Sub
' Main program
Dim g As Graph = GraphNew(4)
AddEdge(g, 0, 1, 10)
AddEdge(g, 0, 2, 6)
AddEdge(g, 0, 3, 5)
AddEdge(g, 1, 3, 15)
AddEdge(g, 2, 3, 4)
BoruvkaMST(g)
Sleep
- Output:
Edge 0-3 With weight 5 included in MST Edge 0-1 With weight 10 included in MST Edge 2-3 With weight 4 included in MST Weight of MST is 19
Java
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public final class BorůvkaAlgorithm {
public static void main(String[] args) {
Graph graph = new Graph(4);
graph.addEdge( new Edge(0, 1, 10.0) );
graph.addEdge( new Edge(0, 2, 6.0) );
graph.addEdge( new Edge(0, 3, 5.0) );
graph.addEdge( new Edge(1, 3, 15.0) );
graph.addEdge( new Edge(2, 3, 4.0) );
graph.borůvkaMinimumSpanningTree();
}
}
final class Graph {
public Graph(int aVertexCount) {
vertexCount = aVertexCount;
edges = new ArrayList<Edge>();
}
public void addEdge(Edge edge) {
edges.addLast(edge);
}
// Return the minimum spanning tree by using Boruvka's algorithm
public void borůvkaMinimumSpanningTree() {
List<Integer> parent = IntStream.range(0, vertexCount).boxed().collect(Collectors.toList());
List<Integer> rank = Stream.generate( () -> 0 ).limit(vertexCount).collect(Collectors.toList());
// Store the indexes of the cheapest edge of each tree
List<Edge> cheapest = IntStream.range(0, vertexCount)
.mapToObj( i -> new Edge(-1, -1, -1.0) ).collect(Collectors.toList());
// Initially there are 'vertexCount' different trees
int treeCount = vertexCount;
int minimumSpanningTreeWeight = 0;
// Combine trees until all trees are combined into a single minimum spanning tree
while ( treeCount > 1 ) {
// Traverse through all edges and update cheapest edge for every tree
for ( Edge edge : edges ) {
final int u = edge.getU();
final int v = edge.getV();
final double weight = edge.getWeight();
final int index1 = find(parent, u);
final int index2 = find(parent, v);
// If the two vertices of the current edge belong to different trees,
// check whether the current edge is cheaper than previous cheapest edges
if ( index1 != index2 ) {
if ( cheapest.get(index1).getWeight() == -1.0 || cheapest.get(index1).getWeight() > weight ) {
cheapest.set(index1, new Edge(u, v, weight));
}
if ( cheapest.get(index2).getWeight() == -1.0 || cheapest.get(index2).getWeight() > weight ) {
cheapest.set(index2, new Edge(u, v, weight));
}
}
}
// Add the cheapest edges to the minimum spanning tree
for ( int vertex = 0; vertex < vertexCount; vertex++ ) {
// Check whether the cheapest edge for current vertex exists
if ( cheapest.get(vertex).getWeight() != -1.0 ) {
final int u = cheapest.get(vertex).getU();
final int v = cheapest.get(vertex).getV();
final double weight = cheapest.get(vertex).getWeight();
final int index1 = find(parent, u);
final int index2 = find(parent, v);
if ( index1 != index2 ) {
minimumSpanningTreeWeight += weight;
unionSet(parent, rank, index1, index2);
System.out.println("Edge " + u + "--" + v + " with weight " + weight
+ " is included in the minimum spanning tree");
treeCount -= 1;
}
}
}
}
System.out.println(System.lineSeparator() + "Weight of minimum spanning tree is " + minimumSpanningTreeWeight);
}
// Return the index of the tree containing 'vertex', using a path compression technique
private int find(List<Integer> parent, int vertex) {
if ( parent.get(vertex) != vertex ) {
parent.set(vertex, find(parent, parent.get(vertex)));
}
return parent.get(vertex);
}
// Form the union by rank of the two trees indexed by u and v
private void unionSet(List<Integer> parent, List<Integer> rank, int u, int v) {
final int uRoot = find(parent, u);
final int vRoot = find(parent, v);
// Attach the smaller rank tree under root of the high rank tree
switch ( Integer.compare(rank.get(uRoot), rank.get(vRoot)) ) {
case -1 -> parent.set(uRoot, vRoot);
case +1 -> parent.set(vRoot, uRoot);
// If ranks are the same, make one the root and increment its rank
case 0 -> { parent.set(vRoot, uRoot); rank.set(uRoot, rank.get(uRoot) + 1); }
}
}
private List<Edge> edges;
private final int vertexCount;
}
record Edge(int u, int v, double weight) {
public int getU() { return u; }
public int getV() { return v; }
public double getWeight() { return weight; }
}
- Output:
Edge 0--3 with weight 5.0 is included in the minimum spanning tree Edge 0--1 with weight 10.0 is included in the minimum spanning tree Edge 2--3 with weight 4.0 is included in the minimum spanning tree Weight of minimum spanning tree is 19
JavaScript
class Edge {
constructor(u, v, weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
getU() {
return this.u;
}
getV() {
return this.v;
}
getWeight() {
return this.weight;
}
}
class Graph {
constructor(vertexCount) {
this.vertexCount = vertexCount;
this.edges = [];
}
addEdge(edge) {
this.edges.push(edge);
}
// Return the minimum spanning tree by using Boruvka's algorithm
borůvkaMinimumSpanningTree() {
const parent = Array.from({ length: this.vertexCount }, (_, i) => i);
const rank = Array(this.vertexCount).fill(0);
// Store the indexes of the cheapest edge of each tree
const cheapest = Array.from({ length: this.vertexCount }, () => new Edge(-1, -1, -1.0));
// Initially there are 'vertexCount' different trees
let treeCount = this.vertexCount;
let minimumSpanningTreeWeight = 0;
// Combine trees until all trees are combined into a single minimum spanning tree
while (treeCount > 1) {
// Traverse through all edges and update cheapest edge for every tree
for (const edge of this.edges) {
const u = edge.getU();
const v = edge.getV();
const weight = edge.getWeight();
const index1 = this.find(parent, u);
const index2 = this.find(parent, v);
// If the two vertices of the current edge belong to different trees,
// check whether the current edge is cheaper than previous cheapest edges
if (index1 !== index2) {
if (cheapest[index1].getWeight() === -1.0 || cheapest[index1].getWeight() > weight) {
cheapest[index1] = new Edge(u, v, weight);
}
if (cheapest[index2].getWeight() === -1.0 || cheapest[index2].getWeight() > weight) {
cheapest[index2] = new Edge(u, v, weight);
}
}
}
// Add the cheapest edges to the minimum spanning tree
for (let vertex = 0; vertex < this.vertexCount; vertex++) {
// Check whether the cheapest edge for current vertex exists
if (cheapest[vertex].getWeight() !== -1.0) {
const u = cheapest[vertex].getU();
const v = cheapest[vertex].getV();
const weight = cheapest[vertex].getWeight();
const index1 = this.find(parent, u);
const index2 = this.find(parent, v);
if (index1 !== index2) {
minimumSpanningTreeWeight += weight;
this.unionSet(parent, rank, index1, index2);
console.log(`Edge ${u}--${v} with weight ${weight} is included in the minimum spanning tree`);
treeCount -= 1;
}
}
}
}
console.log(`\nWeight of minimum spanning tree is ${minimumSpanningTreeWeight}`);
}
// Return the index of the tree containing 'vertex', using a path compression technique
find(parent, vertex) {
if (parent[vertex] !== vertex) {
parent[vertex] = this.find(parent, parent[vertex]);
}
return parent[vertex];
}
// Form the union by rank of the two trees indexed by u and v
unionSet(parent, rank, u, v) {
const uRoot = this.find(parent, u);
const vRoot = this.find(parent, v);
// Attach the smaller rank tree under root of the high rank tree
if (rank[uRoot] < rank[vRoot]) {
parent[uRoot] = vRoot;
} else if (rank[uRoot] > rank[vRoot]) {
parent[vRoot] = uRoot;
} else {
// If ranks are the same, make one the root and increment its rank
parent[vRoot] = uRoot;
rank[uRoot] += 1;
}
}
}
// Main function equivalent
function main() {
const graph = new Graph(4);
graph.addEdge(new Edge(0, 1, 10.0));
graph.addEdge(new Edge(0, 2, 6.0));
graph.addEdge(new Edge(0, 3, 5.0));
graph.addEdge(new Edge(1, 3, 15.0));
graph.addEdge(new Edge(2, 3, 4.0));
graph.borůvkaMinimumSpanningTree();
}
// Run the algorithm
main();
- Output:
Edge 0--3 with weight 5 is included in the minimum spanning tree Edge 0--1 with weight 10 is included in the minimum spanning tree Edge 2--3 with weight 4 is included in the minimum spanning tree Weight of minimum spanning tree is 19
Julia
const Edge = Tuple{Int, Int, Int}
""" Structure to represent a graph """
struct Graph
v::Int # Number of vertices
graph::Vector{Edge} # List of Edges [vertex u, vertex v, weight]
end
Graph(vertices) = Graph(vertices, Vector{Int}[])
""" Function to add an edge to the graph with adjust for basis (1 vs 0) of vertex array """
add_edge!(g::Graph, u, v, wt, adjust = true) = push!(g.graph, (u + adjust, v + adjust, wt))
""" A utility function to find the set of an element i (uses path compression technique) """
function find!(parent::Vector{Int}, i::Int)
parent[i] == i && return i
result = find!(parent, parent[i])
parent[i] = result # Path compression
return result
end
""" A function that performs union __by rank__ of two sets x and y """
function union_set!(parent::Vector{Int}, rank::Vector{Int}, x, y)
x_root = find!(parent, x)
y_root = find!(parent, y)
# Attach smaller rank tree under root of high rank tree
if rank[x_root] < rank[y_root]
parent[x_root] = y_root
elseif rank[x_root] > rank[y_root]
parent[y_root] = x_root
else
# If ranks are the same, make one as root and increment its rank
parent[y_root] = x_root
rank[x_root] += 1
end
end
""" The main function to construct MST using Boruvka's algorithm """
function boruvka_mst!(g::Graph, adjust = true)
parent = collect(1:g.v)
rank = zeros(Int, g.v)
# Initially there are V different trees
# Finally there will be one tree that will be the MST
num_trees = g.v
mst_weight = 0
# Keep combining components (or sets) until all
# components are combined into a single MST
while num_trees > 1
# An array to store the index of the cheapest edge of each subset
# It stores [u, v, w] for each component
cheapest = fill((-1, -1, -1), g.v)
# Traverse through all edges and update
# cheapest edge for every component
for (u, v, w) in g.graph
set1 = find!(parent, u)
set2 = find!(parent, v)
# If two corners of current edge belong to different sets,
# check if current edge is cheaper than previous cheapest edges
if set1 != set2
if cheapest[set1][begin+2] == -1 || cheapest[set1][begin+2] > w
cheapest[set1] = (u, v, w)
end
if cheapest[set2][begin+2] == -1 || cheapest[set2][begin+2] > w
cheapest[set2] = (u, v, w)
end
end
end
# Consider the picked cheapest edges and add them to the MST
for vtx in 1:g.v
# Check if cheapest edge for current set exists
if cheapest[vtx][begin+2] != -1
u, v, w = cheapest[vtx]
set1 = find!(parent, u)
set2 = find!(parent, v)
if set1 != set2
mst_weight += w
union_set!(parent, rank, set1, set2)
# adjust vertex numbers in output to match original edge array basis of 0
println("Edge $(u-adjust)->$(v-adjust) with weight $w is included in MST")
num_trees -= 1
end
end
end
println("Weight of MST is ", mst_weight)
end
end
function test_mst()
g = Graph(4)
add_edge!(g, 0, 1, 10)
add_edge!(g, 0, 2, 6)
add_edge!(g, 0, 3, 5)
add_edge!(g, 1, 3, 15)
add_edge!(g, 2, 3, 4)
boruvka_mst!(g)
end
test_mst()
- Output:
Edge 0->3 with weight 5 is included in MST Edge 0->1 with weight 10 is included in MST Edge 2->3 with weight 4 is included in MST Weight of MST is 19
Phix
-- the graph
integer v -- Number of vertices
sequence edges -- List of Edges (vertex u, vertex v, weight)
-- working variables
sequence parent, rank
function find_parent(integer i)
-- A utility function to find the set of an element i (uses path compression technique)
if parent[i] == i then return i end if
integer result = find_parent(parent[i])
parent[i] = result -- Path compression
return result
end function
procedure union_set(integer x, y)
-- A function that performs union __by rank__ of two sets x and y
integer x_root = find_parent(x),
y_root = find_parent(y)
-- Attach smaller rank tree under root of high rank tree
if rank[x_root] < rank[y_root] then
parent[x_root] = y_root
elsif rank[x_root] > rank[y_root] then
parent[y_root] = x_root
else
-- If ranks are the same, make one as root and increment its rank
parent[y_root] = x_root
rank[x_root] += 1
end if
end procedure
procedure boruvka_minimum_spanning_tree()
-- The main function to construct MST using Boruvka's algorithm
parent = tagset(v)
rank = repeat(0,v)
-- Initially there are V different trees
--- Finally there will be one tree that will be the MST
integer num_trees = v,
mst_weight = 0
-- Keep combining components (or sets) until all
-- components are combined into a single MST
while num_trees > 1 do
-- An array to store the index of the cheapest edge of each subset
-- It stores [u, v, w] for each component
sequence cheapest = repeat({-1, -1, -1},v)
-- Traverse through all edges and update
-- cheapest edge for every component
for edge in edges do
integer {u, v, w} = edge,
set1 = find_parent(u),
set2 = find_parent(v)
-- If two corners of current edge belong to different sets,
-- check if current edge is cheaper than previous cheapest edges
if set1 != set2 then
if cheapest[set1][3] == -1 or cheapest[set1][3] > w then
cheapest[set1] = {u, v, w}
end if
if cheapest[set2][3] == -1 or cheapest[set2][3] > w then
cheapest[set2] = {u, v, w}
end if
end if
end for
-- Consider the picked cheapest edges and add them to the MST
for vtx=1 to v do
-- Check if cheapest edge for current set exists
if cheapest[vtx][3] != -1 then
integer {u, v, w} = cheapest[vtx],
set1 = find_parent(u),
set2 = find_parent(v)
if set1 != set2 then
mst_weight += w
union_set(set1, set2)
-- adjust vertex numbers in output to match 0-based indexing
printf(1,"Edge %d -> %d with weight %d is included in MST\n",{u-1,v-1,w})
num_trees -= 1
end if
end if
end for
printf(1,"Weight of MST is %d\n", mst_weight)
end while
end procedure
v = 4
edges = {{1, 2, 10},
{1, 3, 6},
{1, 4, 5},
{2, 4, 15},
{3, 4, 4}}
boruvka_minimum_spanning_tree()
- Output:
Edge 0 -> 3 with weight 5 is included in MST Edge 0 -> 1 with weight 10 is included in MST Edge 2 -> 3 with weight 4 is included in MST Weight of MST is 19
Rust
// Structure to represent a graph
struct Graph {
v: usize, // Number of vertices
graph: Vec<Vec<i32>>, // List of edges [u, v, w]
}
impl Graph {
fn new(vertices: usize) -> Self {
Graph {
v: vertices,
graph: Vec::new(),
}
}
// Function to add an edge to the graph
fn add_edge(&mut self, u: i32, v: i32, w: i32) {
self.graph.push(vec![u, v, w]);
}
// A utility function to find the set of an element i
// (uses path compression technique)
fn find(&self, parent: &mut Vec<usize>, i: usize) -> usize {
if parent[i] == i {
return i;
}
let result = self.find(parent, parent[i]);
parent[i] = result; // Path compression
result
}
// A function that performs union of two sets x and y
// (uses union by rank)
fn union_set(&self, parent: &mut Vec<usize>, rank: &mut Vec<usize>, x: usize, y: usize) {
let x_root = self.find(parent, x);
let y_root = self.find(parent, y);
// Attach smaller rank tree under root of high rank tree
if rank[x_root] < rank[y_root] {
parent[x_root] = y_root;
} else if rank[x_root] > rank[y_root] {
parent[y_root] = x_root;
} else {
// If ranks are the same, make one as root and increment its rank
parent[y_root] = x_root;
rank[x_root] += 1;
}
}
// The main function to construct MST using Boruvka's algorithm
fn boruvka_mst(&self) {
let mut parent: Vec<usize> = (0..self.v).collect();
let mut rank: Vec<usize> = vec![0; self.v];
// An array to store the index of the cheapest edge of each subset
// It stores [u, v, w] for each component
let mut cheapest: Vec<Vec<i32>> = vec![vec![-1, -1, -1]; self.v];
// Initially there are V different trees
// Finally there will be one tree that will be the MST
let mut num_trees = self.v;
let mut mst_weight = 0;
// Keep combining components (or sets) until all
// components are combined into a single MST
while num_trees > 1 {
// Traverse through all edges and update
// cheapest edge for every component
for edge in &self.graph {
let u = edge[0] as usize;
let v = edge[1] as usize;
let w = edge[2];
let set1 = self.find(&mut parent, u);
let set2 = self.find(&mut parent, v);
// If two corners of current edge belong to different sets,
// check if current edge is cheaper than previous cheapest edges
if set1 != set2 {
if cheapest[set1][2] == -1 || cheapest[set1][2] > w {
cheapest[set1] = vec![u as i32, v as i32, w];
}
if cheapest[set2][2] == -1 || cheapest[set2][2] > w {
cheapest[set2] = vec![u as i32, v as i32, w];
}
}
}
// Consider the picked cheapest edges and add them to the MST
for node in 0..self.v {
// Check if cheapest edge for current set exists
if cheapest[node][2] != -1 {
let u = cheapest[node][0] as usize;
let v = cheapest[node][1] as usize;
let w = cheapest[node][2];
let set1 = self.find(&mut parent, u);
let set2 = self.find(&mut parent, v);
if set1 != set2 {
mst_weight += w;
self.union_set(&mut parent, &mut rank, set1, set2);
println!("Edge {}-{} with weight {} included in MST", u, v, w);
num_trees -= 1;
}
}
}
// Reset cheapest array for next iteration
for node in 0..self.v {
cheapest[node][2] = -1;
}
}
println!("Weight of MST is {}", mst_weight);
}
}
fn main() {
let mut g = Graph::new(4);
g.add_edge(0, 1, 10);
g.add_edge(0, 2, 6);
g.add_edge(0, 3, 5);
g.add_edge(1, 3, 15);
g.add_edge(2, 3, 4);
g.boruvka_mst();
}
- Output:
Edge 0-3 with weight 5 included in MST Edge 0-1 with weight 10 included in MST Edge 2-3 with weight 4 included in MST Weight of MST is 19
Wren
// Class to represent a graph
class Graph {
construct new(vertices) {
_v = vertices // number of vertices
_graph = [] // list of edges [u, v, w]
}
// Method to add an edge to the graph.
addEdge(u, v, w) {
_graph.add([u, v, w])
}
// A utility method to find the set of an element i
// (uses path compression technique).
find(parent, i) {
if (parent[i] == i) return i
var result = find(parent, parent[i])
parent[i] = result // path compression
return result
}
// A method that performs union of two sets x and y
// (uses union by rank).
unionSet(parent, rank, x, y) {
var xRoot = find(parent, x)
var yRoot = find(parent, y)
// Attach smaller rank tree under root of high rank tree.
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot
} else {
// If ranks are the same, make one as root and increment its rank.
parent[yRoot] = xRoot
rank[xRoot] = rank[xRoot] + 1
}
}
// The main method to construct MST using Boruvka's algorithm.
boruvkaMst() {
var parent = (0..._v).map { |i| i }.toList
var rank = List.filled(_v, 0)
// An array to store the index of the cheapest edge of each subset
// It stores [u, v, w] for each component.
var cheapest = List.filled(_v, null)
for (i in 0..._v) cheapest[i] = [-1, -1, -1]
// Initially there are V different trees
// Finally there will be one tree that will be the MST.
var numTrees = _v
var mstWeight = 0
// Keep combining components (or sets) until all
// components are combined into a single MST.
while (numTrees > 1) {
// Traverse through all edges and update
// cheapest edge for every component.
for (edge in _graph) {
var u = edge[0]
var v = edge[1]
var w = edge[2]
var set1 = find(parent, u)
var set2 = find(parent, v)
// If two corners of current edge belong to different sets,
// check if current edge is cheaper than previous cheapest edges.
if (set1 != set2) {
if (cheapest[set1][2] == -1 || cheapest[set1][2] > w) {
cheapest[set1] = [u, v, w]
}
if (cheapest[set2][2] == -1 || cheapest[set2][2] > w) {
cheapest[set2] = [u, v, w]
}
}
}
// Consider the picked cheapest edges and add them to the MST.
for (node in 0..._v) {
// Check if cheapest edge for current set exists.
if (cheapest[node][2] != -1) {
var u = cheapest[node][0]
var v = cheapest[node][1]
var w = cheapest[node][2]
var set1 = find(parent, u)
var set2 = find(parent, v)
if (set1 != set2) {
mstWeight = mstWeight + w
unionSet(parent, rank, set1, set2)
System.print("Edge %(u)-%(v) with weight %(w) included in MST")
numTrees = numTrees - 1
}
}
}
// Reset cheapest array for next iteration.
for (node in 0..._v) cheapest[node][2] = -1
}
System.print("Weight of MST is %(mstWeight)")
}
}
var g = Graph.new(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
g.boruvkaMst()
- Output:
Edge 0-3 with weight 5 included in MST Edge 0-1 with weight 10 included in MST Edge 2-3 with weight 4 included in MST Weight of MST is 19
Zig
const std = @import("std");
const Edge = struct {
u: u32,
v: u32,
weight: f64,
};
const Graph = struct {
edges: std.ArrayList(Edge),
vertex_count: u32,
allocator: std.mem.Allocator,
fn init(allocator: std.mem.Allocator, vertex_count: u32) !Graph {
return Graph{
.edges = std.ArrayList(Edge).init(allocator),
.vertex_count = vertex_count,
.allocator = allocator,
};
}
fn deinit(self: *Graph) void {
self.edges.deinit();
}
fn addEdge(self: *Graph, edge: Edge) !void {
try self.edges.append(edge);
}
// Return the index of the tree containing 'vertex', using a path compression technique
fn find(parent: []u32, vertex: u32) u32 {
if (parent[vertex] != vertex) {
parent[vertex] = find(parent, parent[vertex]);
}
return parent[vertex];
}
// Form the union by rank of the two trees indexed by u and v
fn unionSet(parent: []u32, rank: []u32, u: u32, v: u32) void {
const uRoot = find(parent, u);
const vRoot = find(parent, v);
// Attach the smaller rank tree under root of the high rank tree
if (rank[uRoot] < rank[vRoot]) {
parent[uRoot] = vRoot;
} else if (rank[uRoot] > rank[vRoot]) {
parent[vRoot] = uRoot;
} else {
// If ranks are the same, make one the root and increment its rank
parent[vRoot] = uRoot;
rank[uRoot] += 1;
}
}
// Return the minimum spanning tree by using Boruvka's algorithm
fn boruvkaMinimumSpanningTree(self: *Graph) !void {
const stdout = std.io.getStdOut().writer();
var parent = try self.allocator.alloc(u32, self.vertex_count);
defer self.allocator.free(parent);
var rank = try self.allocator.alloc(u32, self.vertex_count);
defer self.allocator.free(rank);
var cheapest = try self.allocator.alloc(Edge, self.vertex_count);
defer self.allocator.free(cheapest);
// Initialize parent array (each vertex is its own parent)
for (0..self.vertex_count) |i| {
parent[i] = @intCast(i);
rank[i] = 0;
cheapest[i] = Edge{ .u = std.math.maxInt(u32), .v = std.math.maxInt(u32), .weight = -1.0 };
}
// Initially there are 'vertex_count' different trees
var tree_count: u32 = self.vertex_count;
var minimum_spanning_tree_weight: f64 = 0.0;
// Combine trees until all trees are combined into a single minimum spanning tree
while (tree_count > 1) {
// Traverse through all edges and update cheapest edge for every tree
for (self.edges.items) |edge| {
const u = edge.u;
const v = edge.v;
const weight = edge.weight;
const index1 = find(parent, u);
const index2 = find(parent, v);
// If the two vertices of the current edge belong to different trees,
// check whether the current edge is cheaper than previous cheapest edges
if (index1 != index2) {
if (cheapest[index1].weight == -1.0 or cheapest[index1].weight > weight) {
cheapest[index1] = Edge{ .u = u, .v = v, .weight = weight };
}
if (cheapest[index2].weight == -1.0 or cheapest[index2].weight > weight) {
cheapest[index2] = Edge{ .u = u, .v = v, .weight = weight };
}
}
}
// Add the cheapest edges to the minimum spanning tree
for (0..self.vertex_count) |vertex_usize| {
const vertex = @as(u32, @intCast(vertex_usize));
// Check whether the cheapest edge for current vertex exists
if (cheapest[vertex].weight != -1.0) {
const u = cheapest[vertex].u;
const v = cheapest[vertex].v;
const weight = cheapest[vertex].weight;
const index1 = find(parent, u);
const index2 = find(parent, v);
if (index1 != index2) {
minimum_spanning_tree_weight += weight;
unionSet(parent, rank, index1, index2);
try stdout.print("Edge {d}--{d} with weight {d} is included in the minimum spanning tree\n", .{ u, v, weight });
tree_count -= 1;
}
}
}
// Reset cheapest edges for next iteration
for (0..self.vertex_count) |i| {
cheapest[i] = Edge{ .u = std.math.maxInt(u32), .v = std.math.maxInt(u32), .weight = -1.0 };
}
}
try stdout.print("\nWeight of minimum spanning tree is {d}\n", .{minimum_spanning_tree_weight});
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var graph = try Graph.init(allocator, 4);
defer graph.deinit();
try graph.addEdge(Edge{ .u = 0, .v = 1, .weight = 10.0 });
try graph.addEdge(Edge{ .u = 0, .v = 2, .weight = 6.0 });
try graph.addEdge(Edge{ .u = 0, .v = 3, .weight = 5.0 });
try graph.addEdge(Edge{ .u = 1, .v = 3, .weight = 15.0 });
try graph.addEdge(Edge{ .u = 2, .v = 3, .weight = 4.0 });
try graph.boruvkaMinimumSpanningTree();
}
- Output:
Edge 0--3 with weight 5 is included in the minimum spanning tree Edge 0--1 with weight 10 is included in the minimum spanning tree Edge 2--3 with weight 4 is included in the minimum spanning tree Weight of minimum spanning tree is 19