Class PrimMinimumSpanningTree<V,E>

java.lang.Object
org.jgrapht.alg.spanning.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