最小生成树

最小生成树用于在无向带权连通图中选择若干条边，使所有顶点连通，并且总权重最小。Baseline 中包含 Prim 和 Kruskal 两个算法。

最小生成树的输出不一定唯一。只要选出的边来自输入图、能够连通所有顶点、不成环，并且总权重最小，就是合法答案。

Prim

Prim 从一个顶点集合出发，每轮选择一条代价最小的边，把一个新顶点接入当前生成树。课程 Baseline 规定从 0 号顶点开始。

Prim 过程：从 A 开始

1/7

对应过程：

1. 先把起点 A 加入生成树。
2. 在所有从树内顶点连向树外顶点的边中，选择权重最小的 A-B。
3. A-C 与 A-B 等权，用来强调 MST 在等权边场景下可能不唯一。
4. 继续选择连接树外顶点的低权边 B-D。
5. D-E 权重为 1，会优先接入。
6. D-F 和 E-F 等权，任选一条都可能得到合法 MST。
7. 最后接入 G，当选入边数达到 vertex_count - 1 时生成树完成。

Prim 实现时常用三个数组：

• selected[]：顶点是否已经加入生成树。
• best_weight[]：未选顶点连接到当前生成树的最小边权。
• parent[]：未选顶点当前最优连接边来自哪个顶点。

Baseline 中需要补全 Prim(graph, mst_edges, total_cost)。连通图返回 1；不连通图返回 0；单顶点图返回 1，并令 total_cost = 0。

运行方式：

make test-prim

Kruskal

Kruskal 从边集合出发，按权重从小到大尝试加入边。如果加入某条边会形成环，就跳过它。这个“是否已经连通”的判断由并查集完成。

Kruskal 过程：边按权重排序

1/8

对应过程：

1. 把所有边按权重从小到大排序。
2. 先选择权重为 1 的 D-E。
3. 再选择权重为 1 的 F-G。
4. 处理等权三角形中的 A-B。
5. 继续选择 A-C。
6. 检查 B-C 时，B 和 C 已经通过 A 连通，加入会成环，因此跳过。
7. 选择 B-D 把左侧组件和中间组件连起来。
8. 再选择一条连接右侧组件的边，生成树完成。

Baseline 中需要补全：

• DisjointSet::Find：查找集合代表，建议使用路径压缩。
• DisjointSet::Union：合并两个不同集合；若两个顶点已经在同一集合中，返回 false。
• Kruskal(edges, edge_count, vertex_count, mst_edges, total_cost)：按边权从小到大选择不会成环的边。

连通图返回 1；不连通图或非法顶点编号返回 0；单顶点图返回 1，并令 total_cost = 0。

运行方式：

make test-kruskal

输入输出

Prim 和 Kruskal 的输入格式一致：

case_count
vertex_count edge_count
from to weight
...

测试程序输出：

CASE 1
OK 1
TOTAL 16
EDGE_COUNT 4
from to weight
...

OK 表示是否成功得到最小生成树。成功时，后续边应构成一棵合法 MST；失败时 EDGE_COUNT 为 0。

Prim 与 Kruskal 的区别

算法	思路	适合理解为
Prim	从一个顶点集合向外扩展	每轮接入一个新顶点
Kruskal	从最小边开始筛选	每轮尝试加入一条边

调试重点

• 成功时是否输出 vertex_count - 1 条边。
• 输出边是否都来自输入图。
• 输出边是否连通所有顶点。
• 输出边是否成环。
• 总权重是否最小。
• 不连通图是否能返回失败。

运行与作业指导

本页对应 Prim 和 Kruskal 模块。完成相关 TODO 后，建议运行 make test-prim 和 make test-kruskal。

完整的 Baseline、Project、输入输出规范和报告要求见：运行与作业指导。