一种用于查找图的最小长度生成树的算法。它按成本递增的顺序对图的边进行排序，然后重复添加连接不同组件的边，直到图完全连接（Pemmaraju 和 Skiena 2003，第 336 页）。通过对每条边的权重取反，该算法也可用于查找最大生成树。
克鲁斯卡尔算法在 Wolfram 语言中实现为FindSpanningTree[g,Method -> "Kruskal"].
克鲁斯卡尔算法
另请参阅
克鲁斯卡尔树定理, 最大生成树, 最小生成树, 生成树使用 探索
参考文献
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. 和 Skiena, S. "克鲁斯卡尔算法。" §8.2.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 336-338, 2003.在 上被引用
克鲁斯卡尔算法请这样引用
Weisstein, Eric W. "克鲁斯卡尔算法。" 来自 --一个 资源。 https://mathworld.net.cn/KruskalsAlgorithm.html