Package com.jgalgo.alg.span

Class MinimumSpanningTreeBoruvka

java.lang.Object

com.jgalgo.alg.span.MinimumSpanningTreeAbstract

com.jgalgo.alg.span.MinimumSpanningTreeBoruvka

All Implemented Interfaces:

MinimumSpanningTree

public class MinimumSpanningTreeBoruvka
extends MinimumSpanningTreeAbstract

Boruvka minimum spanning tree algorithm.

The algorithm run in iterations. In each iteration it finds the minimum edge incident for each vertex, and adds all of these edges to the forest. Each connected component in the forest become a 'super vertex' in the next iteration. The algorithm terminate when there is a single super vertex in the case the original graph was connected, or when there are no incident edges to the remaining super vertices.

The running time of the algorithm is \(O(m \log n)\) and it uses linear space. Note that only undirected graphs are supported.

Based on "O jistém problému minimálním" [About a certain minimal problem] by Borůvka, Otakar (1926).

Author:

Barak Ugav

See Also:

• Wikipedia

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.span.MinimumSpanningTree

MinimumSpanningTree.IResult, MinimumSpanningTree.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
MinimumSpanningTreeBoruvka()	Construct a new MST algorithm object.

Method Summary

Methods inherited from class com.jgalgo.alg.span.MinimumSpanningTreeAbstract

computeMinimumSpanningTree

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MinimumSpanningTreeBoruvka

public MinimumSpanningTreeBoruvka()

Construct a new MST algorithm object.

Please prefer using MinimumSpanningTree.newInstance() to get a default implementation for the MinimumSpanningTree interface.