Module org.jgrapht.core

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 type

E - the graph edge type

All Implemented Interfaces:

SpanningTreeAlgorithm<E>

public class KruskalMinimumSpanningTree<V,E>
extends 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

Modifier and Type	Method	Description
SpanningTreeAlgorithm.SpanningTree<E>	getSpanningTree()	Computes a spanning tree.

Methods inherited from class java.lang.Object

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

Constructor Details

KruskalMinimumSpanningTree

public KruskalMinimumSpanningTree(Graph<V,E> graph)

Construct a new instance of the algorithm.

Parameters:

graph - the input graph

Method Details

getSpanningTree

public SpanningTreeAlgorithm.SpanningTree<E> getSpanningTree()

Computes a spanning tree.

Specified by:

getSpanningTree in interface SpanningTreeAlgorithm<V>

Returns:

a spanning tree