Module org.jgrapht.core

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 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

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

Modifier and Type	Method	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 Details

PrimMinimumSpanningTree

public PrimMinimumSpanningTree(Graph<V,E> graph)

Construct a new instance of the algorithm.

Parameters:

graph - the input graph

Method Details

getSpanningTree

public SpanningTreeAlgorithm.SpanningTree<E> getSpanningTree()

Computes a spanning tree.

Specified by:

getSpanningTree in interface SpanningTreeAlgorithm<V>

Returns:

a spanning tree