Package org.jgrapht.alg.spanning
Class KruskalMinimumSpanningTree<V,E>
- java.lang.Object
-
- org.jgrapht.alg.spanning.KruskalMinimumSpanningTree<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
SpanningTreeAlgorithm<E>
public class KruskalMinimumSpanningTree<V,E> extends java.lang.Object implements SpanningTreeAlgorithm<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.- Author:
- Tom Conerly
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.SpanningTreeAlgorithm
SpanningTreeAlgorithm.SpanningTree<E>, SpanningTreeAlgorithm.SpanningTreeImpl<E>
-
-
Constructor Summary
Constructors Constructor Description KruskalMinimumSpanningTree(Graph<V,E> graph)
Construct a new instance of the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description SpanningTreeAlgorithm.SpanningTree<E>
getSpanningTree()
Computes a spanning tree.
-
-
-
Method Detail
-
getSpanningTree
public SpanningTreeAlgorithm.SpanningTree<E> getSpanningTree()
Computes a spanning tree.- Specified by:
getSpanningTree
in interfaceSpanningTreeAlgorithm<V>
- Returns:
- a spanning tree
-
-