主题
Search

最小生成树

加权图的最小生成树是总权重最小的一组边，它们构成该图的生成树。当图是无权图时，任何生成树都是最小生成树。

最小生成树可以在多项式时间内找到。常用算法包括 Prim (1957) 算法和 Kruskal 算法 (Kruskal 1956)。该问题也可以使用拟阵来公式化 (Papadimitriou and Steiglitz 1982)。可以使用 Wolfram 语言中的以下命令找到最小生成树FindSpanningTree[g]。

电视剧 NUMB3RS (数字追凶) 的 第一季 剧集 "Vector" 和 "Man Hunt" (2005) 以及 第二季 剧集 "Rampage" (2006) 都以最小生成树为特色。

参见

最大生成树, Kruskal 算法, 生成树

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

最小生成树

请引用为

Weisstein, Eric W. "最小生成树。" 来自 MathWorld--一个 Wolfram 网络资源。 https://mathworld.net.cn/MinimumSpanningTree.html

学科分类