大门|大门-CS-2003 |问题90

下图中最小生成树的权重是多少？

（A） 29 （B） 31 （C） 38 （D） 41 答复: （B） 说明： （a，c）、（a，d）、（d，b）、（b，g）、（g，h）、（h，f）、（h，i）、（i，j）、（i，e）=31

背景要求-最小生成树( 拘谨的 / 克鲁斯卡尔 )

在这类问题中，一定要使用kruskal的算法来找出最小生成树，因为这很容易，而且犯愚蠢错误的可能性较小。

算法：

如果没有形成循环，请始终选择最小边权重，并尝试添加到当前林（树集合）。 一旦你给森林添加了n-1条边，停下来，你就得到了你的最小生成树。

请参见下图，了解该问题的MST构造。

最小生成树的权重=最小生成树中所有边的和 = 31

这一解释由 Pranjul Ahuja。

访问以下链接了解更多信息： http://www.ics.uci.edu/~eppstein/161/960206。html https://en.wikipedia.org/wiki/Minimum_spanning_tree

这个问题的小测验