GESP 八级 · GESP202609 C++ 八级 第 10 题

某连通带权无向简单图的边集合为 $\{(1,2,5),(1,3,1),(2,3,3),(2,4,4),(3,4,2),(3,5,6),(4,5,7)\}$，其中，每条边的三元组 (u,v,w) 表示结点 u 和结点 v 之间有一条权值为 w 的无向边。使用 Kruskal 算法按边权从小到大扫描，第 3 条被选入最小生成树的边是（　　）。

看到题先想：边权排序→并查集维护连通性→依次选不构成环的边。排序后边序为：(1,3,1)、(3,4,2)、(2,3,3)、(2,4,4)、(1,2,5)、(3,5,6)、(4,5,7)。并查集初始每个结点独立。选 (1,3,1) 合并 {1,3}；选 (3,4,2) 合并 {1,3,4}；选 (2,3,3) 合并 {1,2,3,4}；选 (2,4,4) 时 2 与 4 已在同一集合，跳过；选 (1,2,5) 时 1 与 2 已在同一集合，跳过；选 (3,5,6) 合并 {1,2,3,4,5}；选 (4,5,7) 时 4 与 5 已在同一集合，跳过。第 3 条被选入的边是 (2,3,3)。

选项 C (3,4,2) 是第 2 条被选入的边，命题人利用"边权小就一定先被选"的直觉陷阱。选项 A (1,2,5) 是排序后第 5 条边，但并查集状态已使 1 与 2 连通，故被跳过。选项 D (4,5,7) 同理被跳过。最阴险的细节是"第 3 条被选入的边"而非"第 3 条边"，考生易数错。

考纲定位

GESP 八级大纲"图论算法"模块，命题人卡住的是学生对 Kruskal 算法并查集状态更新的掌握——多数考生只背"按权值排序选边"，却忽略每次选边后必须合并集合，导致后续判断错误。

解题思维

看到题先想：边权排序→并查集维护连通性→依次选不构成环的边。排序后边序为：(1,3,1)、(3,4,2)、(2,3,3)、(2,4,4)、(1,2,5)、(3,5,6)、(4,5,7)。并查集初始每个结点独立。选 (1,3,1) 合并 {1,3}；选 (3,4,2) 合并 {1,3,4}；选 (2,3,3) 合并 {1,2,3,4}；选 (2,4,4) 时 2 与 4 已在同一集合，跳过；选 (1,2,5) 时 1 与 2 已在同一集合，跳过；选 (3,5,6) 合并 {1,2,3,4,5}；选 (4,5,7) 时 4 与 5 已在同一集合，跳过。第 3 条被选入的边是 (2,3,3)。