org.jgrapht.alg

Class PrimMinimumSpanningTree<V,E>

java.lang.Object

org.jgrapht.alg.PrimMinimumSpanningTree<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MinimumSpanningTree<V,E>

public class PrimMinimumSpanningTree<V,E>
extends Object
implements MinimumSpanningTree<V,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.

Since:

Mar 5, 2013

Author:

Alexey Kudinkin

Constructor Summary

Constructors

Constructor and Description
PrimMinimumSpanningTree(Graph<V,E> g) Create and execute a new instance of Prim's algorithm.

Method Summary

Modifier and Type	Method and Description
Set<E>	getMinimumSpanningTreeEdgeSet() Returns edges set constituting the minimum spanning tree/forest
double	getMinimumSpanningTreeTotalWeight() Returns total weight of the minimum spanning tree/forest.

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

Create and execute a new instance of Prim's algorithm.

Parameters:

g - the input graph

Method Detail

getMinimumSpanningTreeEdgeSet

public Set<E> getMinimumSpanningTreeEdgeSet()

Description copied from interface: MinimumSpanningTree

Returns edges set constituting the minimum spanning tree/forest

Specified by:

getMinimumSpanningTreeEdgeSet in interface MinimumSpanningTree<V,E>

Returns:

minimum spanning-tree edges set

getMinimumSpanningTreeTotalWeight

public double getMinimumSpanningTreeTotalWeight()

Description copied from interface: MinimumSpanningTree

Returns total weight of the minimum spanning tree/forest.

Specified by:

getMinimumSpanningTreeTotalWeight in interface MinimumSpanningTree<V,E>

Returns:

minimum spanning-tree total weight