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

java.lang.Object
  extended by org.jgrapht.alg.PrimMinimumSpanningTree<V,E>
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
PrimMinimumSpanningTree(Graph<V,E> g)
           
 
Method Summary
 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)
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


Copyright © 2013. All rights reserved.