V- the graph vertex type
E- the graph edge type
public class BoruvkaMinimumSpanningTree<V,E> extends Object implements SpanningTreeAlgorithm<E>
See the article on wikipedia for more information on the history of the algorithm.
This implementation uses a union-find data structure (with union by rank and path compression heuristic) in order to track components. In graphs where edges have identical weights, edges with equal weights are ordered lexicographically. The running time is $O((E+V) \log V)$ under the assumption that the union-find uses path-compression.
|Constructor and Description|
Construct a new instance of the algorithm.
|Modifier and Type||Method and Description|
Computes a spanning tree.
public SpanningTreeAlgorithm.SpanningTree<E> getSpanningTree()
Copyright © 2018. All rights reserved.