org.jgrapht.alg.spanning

## 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|))$.
Since:
Mar 5, 2013
Author:
Alexandru Valeanu, Alexey Kudinkin

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.SpanningTreeAlgorithm

SpanningTreeAlgorithm.SpanningTree<E>, SpanningTreeAlgorithm.SpanningTreeImpl<E>
• ### Constructor Summary

Constructors
Constructor and Description
PrimMinimumSpanningTree(Graph<V,E> graph)
Construct a new instance of the algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and Description
SpanningTreeAlgorithm.SpanningTree<E> getSpanningTree()
Computes a spanning tree.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### PrimMinimumSpanningTree

public PrimMinimumSpanningTree(Graph<V,E> graph)
Construct a new instance of the algorithm.
Parameters:
graph - the input graph
• ### Method Detail

• #### getSpanningTree

public SpanningTreeAlgorithm.SpanningTree<E> getSpanningTree()
Computes a spanning tree.
Specified by:
getSpanningTree in interface SpanningTreeAlgorithm<E>
Returns:
a spanning tree