主题
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.net.cn/MinimumSpanningTree.html

学科分类