hkucuk

Borůvka's Algorithm: An Efficient Method for Finding Minimum Spanning Trees

March 20, 2024 • ☕️ 5 min read • 🏷 computer, software, algorithm, graph

Translated by author into: English


Borůvka’s algorithm is an efficient graph algorithm. This algorithm, which has an important place in graph theory, creates minimum spanning trees by selecting the smallest weighted edges in a graph and combining these edges. Its basic principle is to divide each node in the graph into trees and then connect these trees to each other.

The operation of the algorithm is quite simple but effective. In the first step, each node is considered as the root of a minimum spanning tree. Then, the lowest weight edges in graph are selected and minimum spanning trees are created using these edges. This process is repeated as the minimum number of spanning trees in graph decreases.

The efficiency of Borůvka’s algorithm may vary depending on the size of the graph. While faster results can be obtained especially for large and dense graph structures, smaller and sparser graf structures. However, the performance of the algorithm can be increased by taking advantage of parallel computing opportunities.

One of the advantages of this algorithm is that it is suitable for parallel computing. Being able to execute steps independently can increase efficiency on parallel processors. Additionally, it has a wide application area in problems of finding minimum spanning trees. Minimum spanning trees play an important role in areas such as creating communication networks and planning electrical networks.

Borůvka’s algorithm provides an effective solution to problems of finding minimum spanning trees. It is considered an important tool in graph theory and is used in various application areas. However, the efficiency of the algorithm may vary depending on the size and structure of the graph.

Working Principle of the Algorithm

Borůvka’s algorithm follows the following steps:

  1. Starting Step: Identifying Roots

    • At the beginning of the algorithm, each node is considered the root of its own minimum spanning tree.
    • Each node of the graph is itself marked as the root of a tree.

  2. Edge Selection Step: Determining the Least Weighted Edges

    • The smallest weighted edges extending from the root of each tree in the graph are determined.
    • From the root of each tree, the one with the smallest weight is selected from the edges connected to that tree.

  3. Joining Edges Step: Joining Trees

    • Minimum spanning trees are merged using the smallest weighted edges determined.
    • Each selected edge joins two different trees to form a larger tree.

  4. Iteration Step: Reassessment

    • If there is more than one minimum spanning tree in the graph, these steps are repeated.
    • In the re-evaluation step, the process is continued by selecting the smallest weighted edges from each tree root and merging the trees.

  5. Finish Step: Creation of Minimum Spanning Trees

    • The algorithm terminates when only one minimum spanning tree remains in the graph or a specified criterion is met.
    • As a result of the algorithm, minimum spanning trees are created using the smallest weighted edges in the graph.
    • As a result of these steps, the minimum spanning trees in the graph are completed.

Algorithm Complexity

The complexity of Borůvka’s algorithm is usually expressed as O(E log V), where E is the number of edges and V is the number of nodes. However, this complexity may vary depending on the density and structural properties of the graph.

Important Informations

  1. Borůvka’s algorithm is suitable for parallel computation because the steps can be executed independently.
  2. This algorithm is widely used in problems requiring tree-based network structure.
  3. Borůvka’s algorithm can be faster than other minimum spanning tree algorithms under certain conditions.

In addition to being an effective method for finding minimum spanning trees, Borůvka’s algorithm is also known for its contributions to graph theory. Its complexity and performance advantages enable it to be used in a variety of problems.

Implementation of Borůvka’s Algorithm in GoLang:

package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	src, dest, weight int
}

type Graph struct {
	V, E int
	edge []Edge
}

func createGraph(V, E int) *Graph {
	graph := &Graph{V: V, E: E}
	graph.edge = make([]Edge, E)
	return graph
}

func find(parent []int, i int) int {
	if parent[i] == -1 {
		return i
	}
	return find(parent, parent[i])
}

func union(parent []int, x, y int) {
	xset := find(parent, x)
	yset := find(parent, y)
	parent[xset] = yset
}

func boruvkaMST(graph *Graph) {
	V, E := graph.V, graph.E
	parent := make([]int, V)
	for i := range parent {
		parent[i] = -1
	}
	cheapest := make([]int, V)
	for i := range cheapest {
		cheapest[i] = -1
	}

	numTrees := V
	minimumCost := 0
	for numTrees > 1 {
		for i := range cheapest {
			cheapest[i] = -1
		}

		for i := 0; i < E; i++ {
			set1 := find(parent, graph.edge[i].src)
			set2 := find(parent, graph.edge[i].dest)

			if set1 != set2 {
				if cheapest[set1] == -1 || graph.edge[cheapest[set1]].weight > graph.edge[i].weight {
					cheapest[set1] = i
				}
				if cheapest[set2] == -1 || graph.edge[cheapest[set2]].weight > graph.edge[i].weight {
					cheapest[set2] = i
				}
			}
		}

		for i := 0; i < V; i++ {
			if cheapest[i] != -1 {
				set1 := find(parent, graph.edge[cheapest[i]].src)
				set2 := find(parent, graph.edge[cheapest[i]].dest)

				if set1 != set2 {
					minimumCost += graph.edge[cheapest[i]].weight
					fmt.Printf("Edge %d-%d included in MST\n", graph.edge[cheapest[i]].src, graph.edge[cheapest[i]].dest)
					union(parent, set1, set2)
					numTrees--
				}
			}
		}
	}
	fmt.Printf("Minimum Cost Spanning Tree: %d\n", minimumCost)
}

func main() {
	V, E := 4, 5
	graph := createGraph(V, E)

	graph.edge[0] = Edge{src: 0, dest: 1, weight: 10}
	graph.edge[1] = Edge{src: 0, dest: 2, weight: 6}
	graph.edge[2] = Edge{src: 0, dest: 3, weight: 5}
	graph.edge[3] = Edge{src: 1, dest: 3, weight: 15}
	graph.edge[4] = Edge{src: 2, dest: 3, weight: 4}

	boruvkaMST(graph)
}

When the program is run, the output will be as follows.

Edge 0-3 included in MST
Edge 0-1 included in MST
Edge 2-3 included in MST
Minimum Cost Spanning Tree: 19

The working version of the program can be accessed here.

Resources