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 TreeExplore with Wolfram|Alpha
WolframAlpha
More things to try:
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 AlgorithmCite this as:
Weisstein, Eric W. "Kruskal's Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KruskalsAlgorithm.html