在图论中，最小生成树 (MST) 的目标非常简单：在一个连通图中，找到一个子图，它既能连通所有节点，又要保证所有边的权值之和最小。
直观地理解：你要为 N 个城市铺设光缆，如何设计路线才能让所有城市通网，且总造价最低？
Prim 算法：领土扩张
核心逻辑：切分性质 (Cut Property)
Prim 算法就像是霉菌的生长。随便选一个点作为“基地”。
观察连接“基地内部”和“外部未知区域”的所有边（我们称之为桥）。
永远只选最短的那座桥，通过它占领新的据点。
重复，直到所有点都被占领。
Prim 维护的是点的集合。
Kruskal 算法：岛屿融合
Kruskal 算法就像是拼图或者岛屿融合。
一开始，每个点都是一座孤独的岛屿。
将所有边按权值从小到大排序。
依次拿出最小的边：
如果这条边连接的是两个不同的岛屿：连接它！ 这两个岛屿从此合并成一个大岛。
如果这条边连接的已经是同一个岛屿：丢弃它！ 因为再连就会形成环（回路），是浪费。
Kruskal 维护的是边的集合和连通分量（通常用并查集实现）。
总结
Prim 适合稠密图（边很多），因为它基于点扩展。
Kruskal 适合稀疏图（边很少），因为它基于边排序。
你也可以使用下面这个图构造器来试试任意图的计算过程：