Package org.jgrapht.alg.spanning
Class PrimMinimumSpanningTree<V,E>
- java.lang.Object
-
- org.jgrapht.alg.spanning.PrimMinimumSpanningTree<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
SpanningTreeAlgorithm<E>
public class PrimMinimumSpanningTree<V,E> extends java.lang.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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.SpanningTreeAlgorithm
SpanningTreeAlgorithm.SpanningTree<E>, SpanningTreeAlgorithm.SpanningTreeImpl<E>
-
-
Constructor Summary
Constructors Constructor Description PrimMinimumSpanningTree(Graph<V,E> graph)
Construct a new instance of the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description SpanningTreeAlgorithm.SpanningTree<E>
getSpanningTree()
Computes a spanning tree.
-
-
-
Method Detail
-
getSpanningTree
public SpanningTreeAlgorithm.SpanningTree<E> getSpanningTree()
Computes a spanning tree.- Specified by:
getSpanningTree
in interfaceSpanningTreeAlgorithm<V>
- Returns:
- a spanning tree
-
-