Kruskal 算法按权值从小到大考察边 (u,v)。使用并查集维护当前连通分量时，若 Find(u) 与 Find(v) 的结果相同，应当（）。
Find(u)=Find(v) 表示两个端点已经处在同一连通分量中，当前森林已有一条路径连接它们；再加入 (u,v) 就会形成环，因此应跳过。
选项分析
正确。同一集合内的两个顶点已有路径，新增边会产生环。
错误。Kruskal 不修改边权，也不会把成环边强制加入。
错误。算法保留所有顶点，只决定哪些边进入生成树。
错误。顶点编号与最小生成树的选边原则无关。
本题为什么容易错
有同学只记得 Kruskal“选最小边”，忘了还要满足不成环。最小边如果连接的是同一连通块，也必须舍弃。
简短答案
Kruskal 算法处理一条边时，怎样用并查集判断是否会成环，正确答案是 A（跳过该边，因为加入后会在当前生成森林中形成环）。Find(u)=Find(v) 表示两个端点已经处在同一连通分量中，当前森林已有一条路径连接它们；再加入 (u,v) 就会形成环，因此应跳过。
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 跳过该边，因为加入后会在当前生成森林中形成环 | 本题正确答案 | 正确。同一集合内的两个顶点已有路径，新增边会产生环。 | 看到题干核心场景时优先联想到它 |
| 必须加入该边，并把所有边权改为 0 | 本题干扰项 | 错误。Kruskal 不修改边权，也不会把成环边强制加入。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 删除顶点 u 和 v，再重新开始算法 | 本题干扰项 | 错误。算法保留所有顶点，只决定哪些边进入生成树。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 只比较顶点编号，编号较小就加入 | 本题干扰项 | 错误。顶点编号与最小生成树的选边原则无关。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 必须加入该边，并把所有边权改为 0：错误。Kruskal 不修改边权，也不会把成环边强制加入。
- 删除顶点 u 和 v，再重新开始算法：错误。算法保留所有顶点，只决定哪些边进入生成树。
- 只比较顶点编号，编号较小就加入：错误。顶点编号与最小生成树的选边原则无关。
知识点详解
Kruskal 从空森林开始，按非递减权值考察边。并查集通过 Find 判断端点所属集合，通过 Union 合并两个不同连通分量。若图连通，最终选择 |V|-1 条边；若选边结束仍存在多个分量，则只能得到最小生成森林。按秩合并和路径压缩能让并查集操作接近常数时间，但不改变算法的正确性。
备考速记
同根会成环，跳过；异根能连树，选边再合并。
Kruskal 在图的判环场景中的作用
Kruskal在本题中的核心价值，是解决“Kruskal 算法按权值从小到大考察边 (u,v)。使用并查集维护当前连通分量时，若 Find(u) 与 Find(v) 的结果相同，应当（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。
同类题怎么考
- 给出边权表，逐步选择最小生成树边。
- 问 Find 相同或不同后应执行跳过还是 Union。
Kruskal 在软件设计师软考中的考法
软考选择题通常不会只考概念定义，还会把Kruskal放到图的判环场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。
解题思路
可以把并查集理解成给每个连通块发一个组号。Find 返回组长：u、v 组长相同，说明它们早就能互相到达，再接一条边一定闭环；组长不同，这条边会把两棵树连起来，可以选中并执行 Union。Kruskal 的贪心是按边权排序，并查集负责快速守住“不成环”这条底线。
考点定位
并查集在 Kruskal 中回答的是“两个端点现在是否已经连通”。同根跳过，不同根选边并 Union。
易错提醒
- 边排序后不做环检测。
- Find 不做路径压缩却误以为答案错误；路径压缩影响效率，不影响连通判断。
- 图不连通时仍声称得到一棵覆盖全部顶点的生成树。
备考提示
- 手算时给每一步写出当前连通分量集合。
- 把 Kruskal 的并查集和拓扑排序的入度法区分开，它们处理的图问题不同。
你可能还想了解
- Kruskal 为什么适合使用并查集？
- Find 相同为什么说明加边会成环？
- 图不连通时 Kruskal 会得到什么？
本文小结
Kruskal考察边(u,v)时，若Find(u)=Find(v)，两个端点已连通，加入该边会形成环，应跳过；根不同才选边并执行Union。