Class KruskalMinimumSpanningTree<V,​E>


  • public class KruskalMinimumSpanningTree<V,​E>
    extends java.lang.Object
    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

      Constructors 
      Constructor Description
      KruskalMinimumSpanningTree​(Graph<V,​E> graph)
      Creates and executes a new KruskalMinimumSpanningTree algorithm instance.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.Set<E> getEdgeSet()
      Returns the edges making up the tree found.
      double getSpanningTreeCost()
      Returns the cost of the minimum spanning tree or forest.
      • 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

      • getEdgeSet

        public java.util.Set<E> getEdgeSet()
        Returns the edges making up the tree found.
        Returns:
        Set of Edges
      • getSpanningTreeCost

        public double getSpanningTreeCost()
        Returns the cost of the minimum spanning tree or forest.
        Returns:
        Cost of the spanning tree