Package com.jgalgo.alg.span

Class MinimumSpanningTreeKargerKleinTarjan

java.lang.Object

com.jgalgo.alg.span.MinimumSpanningTreeAbstract

com.jgalgo.alg.span.MinimumSpanningTreeKargerKleinTarjan

All Implemented Interfaces:

RandomizedAlgorithm, MinimumSpanningTree

public class MinimumSpanningTreeKargerKleinTarjan
extends MinimumSpanningTreeAbstract
implements RandomizedAlgorithm

Karger, Klein and Tarjan randomized linear minimum spanning tree algorithm

The algorithm runs in \(O(n + m)\) expected time, and uses linear space in expectation. In practice, this algorithm is out-performed by almost all simpler algorithms. Note that only undirected graphs are supported.

Based on "A randomized linear-time algorithm to find minimum spanning trees" by Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995).

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.span.MinimumSpanningTree

MinimumSpanningTree.IResult, MinimumSpanningTree.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
MinimumSpanningTreeKargerKleinTarjan()	Create a new MST algorithm object.

Method Summary

Modifier and Type	Method	Description
void	setSeed(long seed)	Sets the seed for the random number generator.

Methods inherited from class com.jgalgo.alg.span.MinimumSpanningTreeAbstract

computeMinimumSpanningTree

Methods inherited from class java.lang.Object

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

Constructor Details

MinimumSpanningTreeKargerKleinTarjan

public MinimumSpanningTreeKargerKleinTarjan()

Create a new MST algorithm object.

Please prefer using MinimumSpanningTree.newInstance() to get a default implementation for the MinimumSpanningTree interface.

Method Details

setSeed

public void setSeed(long seed)

Description copied from interface: RandomizedAlgorithm

Sets the seed for the random number generator.

The algorithm will use the same seed for the random number generator, in order to perform deterministically. Note that if methods of the algorithm are called multiple times, the seed should be set before each call.

Specified by:

setSeed in interface RandomizedAlgorithm

Parameters:

seed - the seed for the random number generator.