DSA 最小生成树
最小生成树问题
最小生成树 (MST) 是指在无向图中连接所有顶点的边集合，且边的总权重最小。
{{ msgDone }}
上面的动画运行 Prim 算法 来找到 MST。另一种找到 MST 的方法是运行 Kruskal 算法，它也适用于非连通图。
它被称为最小生成树，因为它是一个连通的、无环的、无向图，这正是树数据结构的定义。
在现实世界中，找到最小生成树可以帮助我们找到最有效的方式将房屋连接到互联网或电网，或者可以帮助我们找到最快的路线来配送包裹。
MST 思维实验
让我们想象一下，上面动画中的圆圈是还没有通电的村庄，而你想要把它们连接到电网。在一个村庄通电后，电缆必须从该村庄延伸到其他村庄。村庄可以以很多不同的方式连接，每条路线都有不同的成本。
电缆很贵，而为电缆挖沟或在空中拉电缆也很贵。地形肯定是一个挑战，而且也许还有未来维护成本，这取决于电缆最终的位置。
所有这些路线成本可以作为图中的边权重来考虑。每个顶点代表一个村庄，每条边代表两个村庄之间电缆可能经过的路线。
创建了这样的图之后，就可以找到最小生成树 (MST)，这将是将这些村庄连接到电网的最有效方式。
事实上，第一个 MST 算法 (Borůvka 算法) 就是在 1926 年为了解决这个问题而发明的：找到将捷克共和国摩拉维亚历史地区的最佳方式连接到电网。
MST 算法
本教程接下来的两页解释了两种在图中找到最小生成树的算法：Prim 算法 和 Kruskal 算法。
| Prim 算法 | Kruskal 算法 | |
|---|---|---|
| 它能在非连通图中找到 MST（最小生成森林）吗？ | 不能 | 能 |
| 它如何开始？ | MST 从随机选择的顶点开始扩展。 | MST 中的第一条边是权重最低的边。 |
| 它的时间复杂度是多少？ | \(O(V^2)\)，或 \( O( E \cdot \log{V}) \)（优化后） | \( O( E \cdot \log{E} ) \) |
