Package com.jgalgo.alg.span

Class MinimumSpanningTreeFredmanTarjan

java.lang.Object

com.jgalgo.alg.span.MinimumSpanningTreeAbstract

com.jgalgo.alg.span.MinimumSpanningTreeFredmanTarjan

All Implemented Interfaces:

MinimumSpanningTree

public class MinimumSpanningTreeFredmanTarjan
extends MinimumSpanningTreeAbstract

Fredman and Tarjan’s minimum spanning tree algorithm.

The algorithm runs in iterations. In each iteration, multiple runs of the MinimumSpanningTreePrim algorithm will be run (sequently) on the vertices: instead of growing the tree of Prim's algorithm until it connect all vertices, we grow the heap that is used to order the out going edges until it reaches a certain size limit. Once the heap reached the limit, we start Prim's algorithm from another vertex until the new heap reaches the limit, and repeat that until we have a spanning forest. Than, we contract each tree to a single super vertex, and we advance to the next iteration.

The algorithm runs in \(O(m \log^* n)\) time and uses linear space. In practice, MinimumSpanningTreePrim usually out-preform this algorithm. Note that only undirected graphs are supported.

Based on "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms" by M.L. Fredman and R.E. Tarjan.

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
MinimumSpanningTreeFredmanTarjan()	Construct a new MST algorithm object.

Method Summary

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

MinimumSpanningTreeFredmanTarjan

public MinimumSpanningTreeFredmanTarjan()

Construct a new MST algorithm object.

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