Class PrimMinimumSpanningTree<V,​E>

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

    public class PrimMinimumSpanningTree<V,​E>
    extends Object
    implements SpanningTreeAlgorithm<E>
    An implementation of Prim's algorithm that finds a minimum spanning tree/forest subject to connectivity of the supplied weighted undirected graph. The algorithm was developed by Czech mathematician V. Jarník and later independently by computer scientist Robert C. Prim and rediscovered by E. Dijkstra. This implementation relies on a Fibonacci heap, and runs in $O(|E| + |V|log(|V|))$.
    Author:
    Alexandru Valeanu, Alexey Kudinkin