🏷️ 知识点：并查集判环

用 Kruskal 算法求一个带权连通图的最小生成树。在算法执行的某时刻，已选取的边集合为 TE={(1,2),(2,3),(3,5)}。要选取下一条权值最小的边，不可能选取的边是（　　）。

A. (3,6) B. (2,4) C. (1,3) D. (1,4)

[tag_link]

正确答案：C

结论

选 C。

推导

Kruskal 按边权递增尝试加入边，但若候选边的两个端点已经在同一连通分量中，就会形成回路，必须跳过。TE 已使 1、2、3、5 连成一棵树，因此 (1,3) 会闭合回路，不可能被选入；其余边仍可能连接不同分量。

易错点

“权值最小”不等于“必选”：Kruskal 还要检查加入该边是否成环。