org.jgrapht.alg.spanning

Class BoruvkaMinimumSpanningTree<V,E>

java.lang.Object

org.jgrapht.alg.spanning.BoruvkaMinimumSpanningTree<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

SpanningTreeAlgorithm<E>

public class BoruvkaMinimumSpanningTree<V,E>
extends Object
implements SpanningTreeAlgorithm<E>

Borůvka's algorithm for the computation of a minimum spanning tree.

See the article on wikipedia for more information on the history of the algorithm.

This implementation uses a union-find data structure (with union by rank and path compression heuristic) in order to track components. In graphs where edges have identical weights, edges with equal weights are ordered lexicographically. The running time is $O((E+V) \log V)$ under the assumption that the union-find uses path-compression.

Author:

Dimitrios Michail

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.SpanningTreeAlgorithm

SpanningTreeAlgorithm.SpanningTree<E>, SpanningTreeAlgorithm.SpanningTreeImpl<E>

Constructor Summary

Constructors

Constructor and Description
BoruvkaMinimumSpanningTree(Graph<V,E> graph) Construct a new instance of the algorithm.

Method Summary

Modifier and Type	Method and 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 Detail

BoruvkaMinimumSpanningTree

public BoruvkaMinimumSpanningTree(Graph<V,E> graph)

Construct a new instance of the algorithm.

Parameters:

graph - the input graph

Method Detail

getSpanningTree

public SpanningTreeAlgorithm.SpanningTree<E> getSpanningTree()

Computes a spanning tree.

Specified by:

getSpanningTree in interface SpanningTreeAlgorithm<E>

Returns:

a spanning tree