edu.uci.ics.jung.algorithms.shortestpath
Class PrimMinimumSpanningTree<V,E>

java.lang.Object
  edu.uci.ics.jung.algorithms.shortestpath.PrimMinimumSpanningTree<V,E>

Type Parameters:

V - the vertex type

E - the edge type

public class PrimMinimumSpanningTree<V,E>
extends Object

For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.

Author:

Tom Nelson - tomnelson@dev.java.net

Field Summary

protected	treeFactory
protected	weights

Constructor Summary

PrimMinimumSpanningTree( factory)
Creates an instance which generates a minimum spanning tree assuming constant edge weights.

PrimMinimumSpanningTree( factory, weights)
Creates an instance which generates a minimum spanning tree using the input edge weights.

Method Summary

protected V	findRoot(Graph<V,E> graph)
Graph<V,E>	transform(Graph<V,E> graph)
protected void	updateTree(Graph<V,E> tree, Graph<V,E> graph, Collection<E> unfinishedEdges)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

treeFactory

protected  treeFactory

weights

protected  weights

Constructor Detail

PrimMinimumSpanningTree

public PrimMinimumSpanningTree( factory)

Creates an instance which generates a minimum spanning tree assuming constant edge weights.

PrimMinimumSpanningTree

public PrimMinimumSpanningTree( factory,
                                weights)

Creates an instance which generates a minimum spanning tree using the input edge weights.

Method Detail

transform

public Graph<V,E> transform(Graph<V,E> graph)

Parameters:

graph - the Graph to find MST in

findRoot

protected V findRoot(Graph<V,E> graph)

updateTree

protected void updateTree(Graph<V,E> tree,
                          Graph<V,E> graph,
                          Collection<E> unfinishedEdges)