- Type Parameters:
V- the graph vertex type
E- the graph edge type
- All Implemented Interfaces:
public class BoruvkaMinimumSpanningTree<V,E> extends java.lang.Object implements SpanningTreeAlgorithm<E>Borůvka's algorithm for the computation of a minimum spanning tree.
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.
- Dimitrios Michail
All Methods Instance Methods Concrete Methods Modifier and Type Method Description
getSpanningTree()Computes a spanning tree.