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.
-
-
-
Constructor Detail
-
MinimumSpanningTreeKruskal
public MinimumSpanningTreeKruskal()
Construct a new MST algorithm object.Please prefer using
MinimumSpanningTree.newInstance()
to get a default implementation for theMinimumSpanningTree
interface.
-
-