DSA 最小生成树

最小生成树问题

最小生成树（MST）是指连接无向图中所有顶点的边的集合，且这些边的总权重最小。

上面的动画运行了 Prim 算法 来寻找最小生成树。另一种寻找最小生成树的方法，也适用于不连通图，是运行 Kruskal 算法。

它被称为最小生成树，因为它是一个连通的、无环的、无向图，这正是树形数据结构的定义。

在现实世界中，找到最小生成树可以帮助我们找到连接房屋到互联网或电网的最有效方式，或者帮助我们找到递送包裹的最快路线。

最小生成树思想实验

让我们想象一下，上面动画中的圆圈是还没有接入电力的村庄，而你想将它们连接到电网。在一个村庄接入电力后，电缆必须从该村庄延伸到其他村庄。村庄可以通过许多不同的方式连接，每条路线都有不同的成本。

电缆是昂贵的，挖掘电缆沟或在空中铺设电缆也是昂贵的。地形无疑会带来挑战，然后可能还会有因电缆最终位置不同而产生的未来维护成本。

所有这些路线成本都可以作为图中的边权重进行核算。每个顶点代表一个村庄，每条边代表连接两个村庄的电缆的可能路线。

创建了这样的图之后，就可以找到最小生成树（MST），这将是连接这些村庄到电网的最有效方式。

这实际上就是第一个 MST 算法（Borůvka 算法）在 1926 年的用途：寻找连接摩拉维亚（捷克共和国历史区域）到电网的最佳方式。

MST 算法

本教程接下来的两页将解释两种寻找图中最小生成树的算法：Prim 算法和Kruskal 算法。