离散数学最小生成树

如果T是树并且T包含G的所有顶点, 则连通图G的子图T称为G的生成树。

最小生成树

假设G是一个连通权重图, 即为G的每个边分配了一个非负数, 称为边的权重, 然后为G的任何生成树T分配了总权重, 该总权重是通过将边的权重添加到T中获得的。

G的最小生成树是总权重尽可能小的树。

克鲁斯卡尔算法找到最小生成树：该算法找到给定连接加权图G的最小生成树T。

例1：确定如图所示的加权图的最小生成树：

解决方案：使用kruskal算法以递增顺序排列加权图的所有边缘, 并使用G的所有六个顶点初始化生成树T。现在开始在T中添加G的边缘, 这些边缘不会形成循环, 并且权重最小, 直到五个因为有六个顶点, 所以不添加边。

边缘权重是否已添加（B, E）2已添加（C, D）3已添加（A, D）4已添加（C, F）4已添加（B, C）5已添加（E, F）5未添加（A , B）6未添加（D, E）6未添加（A, F）7未添加

步骤1：

第2步：

第三步：

步骤4：

第五步：

步骤6：丢弃边（A, B）, （D, E）和（E, F）, 因为它们将在图中形成循环。

因此, 输出步骤5中的最小生成树形式, 总成本为18。

示例2：找到图G的所有生成树, 然后找到图G中所示的G的最小生成树：

解决方案：图G中共有三棵生成树, 如图所示：

要查找最小生成树, 请使用KRUSKAL算法。最小生成树如图所示：

边缘权重已添加或未添加（E, F）1已添加（A, B）2已添加（C, D）2已添加（B, C）3已添加（D, E）3已添加（B, D）6未添加

第一个是最小范围, 最小权重= 11。