org.apache.commons.graph.spanning
Class Prim

java.lang.Object
  org.apache.commons.graph.spanning.Prim

public final class Prim
extends Object

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.

Constructor Summary

Prim()

Method Summary

static <V extends Vertex,WE extends WeightedEdge<V>> Graph<V,WE>

minimumSpanningTree(WeightedGraph<V,WE> graph) Calculates the minimum spanning tree (or forest) of the input Graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

Prim

public Prim()

Method Detail

minimumSpanningTree

public static <V extends Vertex,WE extends WeightedEdge<V>> Graph<V,WE> minimumSpanningTree(WeightedGraph<V,WE> graph)

Calculates the minimum spanning tree (or forest) of the input Graph.

Type Parameters:

V - the Graph vertices type.

WE - the Graph weighted edges type.

Parameters:

graph - the Graph for which minimum spanning tree (or forest) has to be calculated.

Returns:

the minimum spanning tree (or forest) of the input Graph.