最小生成树

最小生成树（MST）在连通的无向加权图中，用总权重最小的一组边连接全部顶点。它不含环，V 个顶点恰好使用 V - 1 条边。

它与最短路径目标不同：最短路径计算一个源点到各处的最低成本；MST 寻找连接所有顶点的最低总成本网络。最终树中两点间的路径，不一定是原图中两点间的最短路径。

本课在同一张图上比较两种贪心算法。Prim 扩展一棵连通树，每次选边必须跨越树内外的割；Kruskal 从每个顶点一个分量开始，按权重从小到大扫描边，只接受连接不同分量的边。

两种算法如何工作

Prim 用集合 S 保存已加入树的顶点，用最小堆保存前沿边。候选边入队时一端在 S，另一端在外。弹出最轻边后，若外端仍在外，就接受并加入该顶点；若等待期间两端都已进入树，条目过期，应拒绝。

画面左侧直接显示割的两边 S 和 V - S。割性质保证：跨越该割的最轻边可以安全地加入某棵与当前选择兼容的 MST。每加入一个顶点，Prim 就在新割上再次应用这个性质。

Kruskal 先排序全部边，再用并查集判断两端是否已由接受边连通。根不同就接受并合并；根相同说明已有路径相连，新增边会形成环，必须拒绝。

两种算法都允许负权。负边只是优先级更高的候选，仍须满足连接和无环条件。这一点与要求非负权的 Dijkstra 不同。

最小生成树逐步演示

默认桥接预设有 A–F 六个顶点，无向边为 B–C (1)、B–D (2)、C–D (3)、C–E (4)、D–F (5)、D–E (6)、A–C (7)、A–B (8)、E–F (9)。

Prim 从 A 开始：

1. A 加入 S，暴露 A–C (7) 和 A–B (8)。
2. 弹出 A–C (7)，跨越当前割，接受并加入 C，总重 7。新增 C–B (1)、C–D (3)、C–E (4)。
3. 弹出并接受 C–B (1)，加入 B，总重 8，新增 B–D (2)。
4. 接受 B–D (2)，加入 D，总重 10，新增 D–F (5)、D–E (6)。
5. 弹出 C–D (3)。C、D 已通过 C–B、B–D 连通，拒绝该边以防成环。
6. 接受 C–E (4)，加入 E，总重 14，新增 E–F (9)。
7. 接受 D–F (5)，加入 F，总重 19。
8. 已接受 6 - 1 = 5 条边，树完成，停止。此前的安全选择已构成 MST，无需继续处理前沿。

接受边为 A–C、B–C、B–D、C–E、D–F，总重 19。

Kruskal 则先接受 B–C (1)、B–D (2)，因同分量而拒绝 C–D (3)；再接受 C–E (4)、D–F (5)；拒绝成环的 D–E (6)；最后用 A–C (7) 把 A 接入，五条边总重仍为 19。

Prim 受一棵树的当前割约束，Kruskal 可以在图中任意位置连接分量，所以选边顺序不同。本图边权互异，MST 唯一，因此结果相同。

时间与空间复杂度

邻接表加二叉最小堆的 Prim，在本课简单图模型下时间为 O((V + E) log V)，图与堆共占 O(V + E) 空间。懒前沿堆可达 O(E) 项，严格的堆操作为 O(log E)，简单图中可等价写为 O(log V)。

Kruskal 排序为 O(E log E)，按秩合并和路径压缩的并查集操作合计 O(E α(V))，实际输入范围内接近线性。边列表和并查集数组占 O(V + E)。

稠密图已有邻接矩阵时，O(V²) 的 Prim 实现可能合适；稀疏图已有边列表时，Kruskal 往往更直接。

边界情况

• 单顶点：空边集就是生成树，总重 0。
• 图不连通：不存在生成树。Prim 未覆盖全部顶点就耗尽前沿，Kruskal 扫完边仍有多个分量。不连通预设会报告失败，不把部分森林当 MST。
• 相同边权：可能存在不同但等重的 MST。本课保持同权边的输入顺序以固定回放，其他平局顺序也可能得到合法最优树。
• 负权合法：负边预设接受权重 -3 的边，最终总重 3。
• 平行边：分别作为候选，轻边连接两端后，重边会成环。
• 自环：不能连接不同分量，应忽略。

常见错误

1. Prim 选择全图最轻剩余边。两端都在树外的便宜边还不能扩展当前树，只能从当前割选。
2. Kruskal 只看端点是否出现过。要比较两端的并查集根；出现过的端点仍可连接不同分量。
3. 每个顶点都出现在某条接受边中就停止。多个分量也能覆盖全部顶点；在无环条件下，连通图接受 V - 1 条边才完成。
4. 用在有向图上。有向对应问题通常称为最小树形图，需要不同算法。
5. 误以为负权使 Prim、Kruskal 失效。非负限制属于 Dijkstra。
6. 将不连通图的部分森林报告成生成树。最小生成森林有用途，但应按实际结果命名。

动画中的展示方式

Prim 的前沿画成完全排序行，真实二叉堆只有部分有序，保证能取最小值。Kruskal 的整行确实排序，因为全边排序就是算法的一步。

代码面板展示核心流程，假设图、堆、并查集已经实现。动画将堆插入和分量合并拆成独立节拍，便于检查每次状态变化。