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

java.lang.Object
  extended by org.jgrapht.alg.KruskalMinimumSpanningTree<V,E>
All Implemented Interfaces:
MinimumSpanningTree<V,E>

public class KruskalMinimumSpanningTree<V,E>
extends Object
implements MinimumSpanningTree<V,E>

An implementation of Kruskal's minimum spanning tree algorithm. If the given graph is connected it computes the minimum spanning tree, otherwise it computes the minimum spanning forest. The algorithm runs in time O(E log E). This implementation uses the hashCode and equals method of the vertices.

Since:
Feb 10, 2010
Author:
Tom Conerly

Constructor Summary
KruskalMinimumSpanningTree(Graph<V,E> graph)
          Creates and executes a new KruskalMinimumSpanningTree algorithm instance.
 
Method Summary
 Set<E> getEdgeSet()
          Deprecated. 
 Set<E> getMinimumSpanningTreeEdgeSet()
          Returns edges set constituting the minimum spanning tree/forest
 double getMinimumSpanningTreeTotalWeight()
          Returns total weight of the minimum spanning tree/forest.
 double getSpanningTreeCost()
          Deprecated. 
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

KruskalMinimumSpanningTree

public KruskalMinimumSpanningTree(Graph<V,E> graph)
Creates and executes a new KruskalMinimumSpanningTree algorithm instance. An instance is only good for a single spanning tree; after construction, it can be accessed to retrieve information about the spanning tree found.

Parameters:
graph - the graph to be searched
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

getEdgeSet

@Deprecated
public Set<E> getEdgeSet()
Deprecated. 

Returns edges set constituting the minimum spanning tree/forest

Returns:
minimum spanning-tree edges set

getSpanningTreeCost

@Deprecated
public double getSpanningTreeCost()
Deprecated. 

Returns total weight of the minimum spanning tree/forest.

Returns:
minimum spanning-tree total weight


Copyright © 2013. All rights reserved.