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>
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|))$.
-
Nested Class Summary
Nested ClassesNested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.SpanningTreeAlgorithm
SpanningTreeAlgorithm.SpanningTree<E>, SpanningTreeAlgorithm.SpanningTreeImpl<E>
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionPrimMinimumSpanningTree
(Graph<V, E> graph) Construct a new instance of the algorithm. -
Method Summary
Modifier and TypeMethodDescriptionComputes a spanning tree.
-
Field Details
-
g
-
-
Constructor Details
-
PrimMinimumSpanningTree
Construct a new instance of the algorithm.- Parameters:
graph
- the input graph
-
-
Method Details
-
getSpanningTree
Computes a spanning tree.- Specified by:
getSpanningTree
in interfaceSpanningTreeAlgorithm<V>
- Returns:
- a spanning tree
-