TOPICS
Search

Kruskal's Algorithm

An algorithm for finding a graph's spanning tree of minimum length. It sorts the edges of a graph in order of increasing cost and then repeatedly adds edges that bridge separate components until the graph is fully connected (Pemmaraju and Skiena 2003, p. 336). By negating the weights for each edge, the algorithm can also be used to find a maximum spanning tree.

Kruskal's algorithm is implemented in the Wolfram Language as FindSpanningTree[g, Method -> "Kruskal"].

See also

Kruskal's Tree Theorem, Maximum Spanning Tree, Minimum Spanning Tree, Spanning Tree

Explore with Wolfram|Alpha

References

Gardner, M. Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 248-249, 1978.Kruskal, J. B. "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proc. Amer. Math. Soc. 7, 48-50, 1956.Pemmaraju, S. and Skiena, S. "Kruskal's Algorithm." §8.2.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 336-338, 2003.

Referenced on Wolfram|Alpha

Kruskal's Algorithm

Cite this as:

Weisstein, Eric W. "Kruskal's Algorithm." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KruskalsAlgorithm.html

Subject classifications