Package com.jgalgo.alg.span

Class MinimumSpanningTreeKruskal

java.lang.Object

com.jgalgo.alg.span.MinimumSpanningTreeAbstract

com.jgalgo.alg.span.MinimumSpanningTreeKruskal

All Implemented Interfaces:

MinimumSpanningTree

public class MinimumSpanningTreeKruskal
extends MinimumSpanningTreeAbstract

Kruskal's minimum spanning tree algorithm.

The algorithm first sort all the edges of the graph by their weight, and then examine them in increasing weight order. For each examined edge, if it connects two connected components that were not connected beforehand, the edge is added to the forest. The algorithm terminate after all edges were examined.

The running time of the algorithm is \(O(m \log n)\) and it uses linear time. This algorithm perform good in practice and its running time compete with other algorithms such as MinimumSpanningTreePrim, which have better time bounds in theory. Note that only undirected graphs are supported.

Based on "On the shortest spanning subtree of a graph and the traveling salesman problem" by Kruskal, J. B. (1956) in the book "Proceedings of the American Mathematical Society".

Author:

Barak Ugav

See Also:

• Wikipedia

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
MinimumSpanningTreeKruskal()	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

MinimumSpanningTreeKruskal

public MinimumSpanningTreeKruskal()

Construct a new MST algorithm object.

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