主題
Search

最小生成樹

加權圖的最小生成樹是總權重最小的一組邊，它們構成該圖的生成樹。當圖是無權圖時，任何生成樹都是最小生成樹。

最小生成樹可以在多項式時間內找到。常用演算法包括 Prim (1957) 演算法和 Kruskal 演算法 (Kruskal 1956)。該問題也可以使用擬陣來公式化 (Papadimitriou and Steiglitz 1982)。可以使用 Wolfram 語言中的以下命令找到最小生成樹FindSpanningTree[g]。

電視劇 NUMB3RS (數字追兇) 的 第一季 劇集 "Vector" 和 "Man Hunt" (2005) 以及 第二季 劇集 "Rampage" (2006) 都以最小生成樹為特色。

參見

最大生成樹, Kruskal 演算法, 生成樹

使用 探索

參考文獻

Fredman, M. L. and Tarjan, R. E. "Fibonacci Heaps and Their Uses in Network Optimization." J. ACM 34, 596-615, 1987.Graham, R. L. and Hell, P. "On the History of the Minimum Spanning Tree Problem." Ann. History Comput. 7, 43-57, 1985.Kruskal, J. B. "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proc. Amer. Math. Soc. 7, 48-50, 1956.Papadimitriou, C. H. and Steiglitz, K. 組合最佳化：演算法與複雜性。 Englewood Cliffs, NJ: Prentice-Hall, 1982.Pemmaraju, S. and Skiena, S. "Minimum Spanning Trees." §8.2 in 計算離散數學：Mathematica 中的組合學和圖論。 Cambridge, England: Cambridge University Press, pp. 335-336, 2003.Prim, R. C. "Shortest Connection Networks and Some Generalizations." Bell System Tech. J. 36, 1389-1401, 1957.Skiena, S. "Minimum Spanning Tree." §6.2 in 實現離散數學：Mathematica 中的組合學和圖論。 Reading, MA: Addison-Wesley, pp. 232-236, 1990.

在 中被引用

最小生成樹

請引用為

Weisstein, Eric W. "最小生成樹。" 來自 --一個 Wolfram 網路資源。 https://mathworld.tw/MinimumSpanningTree.html

學科分類