Class 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