Package com.jgalgo.alg.span

Class MinimumSpanningTreeYao

java.lang.Object

com.jgalgo.alg.span.MinimumSpanningTreeAbstract

com.jgalgo.alg.span.MinimumSpanningTreeYao

All Implemented Interfaces:

MinimumSpanningTree

public class MinimumSpanningTreeYao
extends MinimumSpanningTreeAbstract

Yao's buckets minimum spanning tree algorithm.

The algorithm runs in $O(m \log \log n + n \log n)$ and uses linear space. Its running time in practice is not the best compared to MinimumSpanningTreeKruskal and MinimumSpanningTreePrim. Note that only undirected graphs are supported.

Based on "An 0(|E|loglog|V|) algorithm for finding minimum spanning trees" by Andrew Chi-chih Yao (1976).

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
MinimumSpanningTreeYao()	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 Detail

MinimumSpanningTreeYao

public MinimumSpanningTreeYao()

Construct a new MST algorithm object.

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