为何Kruskal算法的union过程仍检查r_x=r_y？调用前提已满足find(u)≠find(v)

这其实是出于几个非常实际的工程设计考虑：

• union是独立的公共函数，不能绑定调用场景
  Kruskal只是并查集（Union-Find）结构的一个应用场景而已，union函数本身是并查集的核心操作之一，可能会被其他算法、其他模块调用。如果它不自己做检查，那其他调用方忘记判断的话，就会把同一个集合里的元素重复合并，直接破坏并查集的结构。所以给union加上这个检查，是让它具备防御性编程的能力，不管谁调用都能保证自身逻辑的正确性。

• 应对并发场景下的竞态问题
  如果是在多线程环境下运行Kruskal算法，从if find(u) != find(v)判断通过，到真正执行union(u,v)这中间，可能有其他线程修改了u或v所属的集合。比如另一个线程刚好把u和v合并了，这时候当前线程再执行union就会出错，而union内部的检查就能挡住这种情况，避免非法操作。

• 提升代码的鲁棒性与可维护性
  就算是单线程环境，代码也难免会被修改。比如哪天有人改Kruskal的代码，不小心删掉了前面的find判断，或者写错了判断逻辑，union内部的检查就能作为最后一道防线，防止引入严重bug。而且这样设计的union函数职责更清晰——它自己负责保证“只合并不同集合”这个核心规则，不需要依赖调用者的正确使用。

附原算法代码：

procedure kruskal(G,w):
for all u in V:
    makeset(u)
X={}
sort the edges E by weight
for all edges {u,v} in E:
    if find(u) != find(v)
        add edge {u,v} to X
        union(u,v)


procedure union(x,y):
r_x = find(x)
r_y = find(y)
if r_x = r_y: return
....more code here

内容的提问来源于stack exchange，提问作者OOProg