Package com.jgalgo.alg.span

Class 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