Class BoruvkaMinimumSpanningTree<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    SpanningTreeAlgorithm<E>

    public class BoruvkaMinimumSpanningTree<V,​E>
    extends 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.

    Author:
    Dimitrios Michail