MinimumSpanningTreeBoruvka (JGAlgo - Parent 0.5.1-SNAPSHOT API)

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 Detail
  - MinimumSpanningTreeBoruvka
```
public MinimumSpanningTreeBoruvka()
```
    Construct a new MST algorithm object.
    Please prefer using MinimumSpanningTree.newInstance() to get a default implementation for the MinimumSpanningTree interface.