一種用於查詢圖的最小長度生成樹的演算法。它按成本遞增的順序對圖的邊進行排序，然後重複新增連線不同元件的邊，直到圖完全連線（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.tw/KruskalsAlgorithm.html