顾名思义，并查集的功能是并和查，但并和查的对象是什么呢？针对的是集合。所以我想了一个例子给大家讲解，咱不说概念性晦涩的东西。通俗易懂，直接来看图：
这是我做的一张两个IT公司的公司人员结构，当然两个公司就不用介绍了，现在问题来了：比如我想知道Steve Ballmer和worker4是不是一个公司的该怎么办？我们可以定义一个结构体，里面有个属性叫company来记录一个人的公司，这样就浪费大量的空间；还可以定义一个传统的树形结构来存储每个节点，然后搜索根节点，找到大Boss，然后比较两个Boss如果是同一个人他们就在一个公司，但多次判断两个人在不在同一个公司，或者多次判断某个人在不在某个公司显然又浪费了大量的时间。这时就该我们的并查集登场了，我们假设先把这些人编上号，如下图：
假如我们知道所有的两人的上下级关系，然后我们申请一个set[10]的数组（大于7就可以）我们把所有人存在这个数组里，我们就利用这个set数组记录存在上下级关系的两个人，比如set的下标4就代表worker2(编号为4的人)，而set[4]的值代表worker2(编号为4)的上司steve
ballmer(编号为2)，我们的思想就是找到两个员工顶级Boss，如果Boss是一个人当然就在同一个公司，如果不是一个人，则不在一个公司。比如判断2和7在不在同一个公司，显然set[4]
= 2.set[2] = 1, 1是Mirosoft的Boss；set[7] = 5, 5是Skype的Boss，显然很容易判断他们不在公司（包含判断4在不在Mirosoft的问题）。这便是并查集“查”的功能。
下面我们来看“并”是什么意思。大家都知道Mirosoft在2011年5月收购了Skype。但是过程是怎么样的呢？我来给大家讲个小故事（以下故事存属虚构）：话说一天worker3找到worker4说想让Mirosoft收购Skype。但他们做不了主，于是他们分别知道了他们的直接上司，worker3找到了Tony
Bates，他是大Boss有权力答应这事而且也同意了，但是worker2的上司是Steve Ballmer他没权利，于是他把这事告诉了他的直接上司Bill
Gates。于是Bill Gates和Tony Bates一拍桌子，行！于是Tony Bates当了Bill
Gates的直接下属，如下图：
但是收购成功之前，由于Worker2的收购想法，Bill Gates决定给Worker2及Worker2的上司，和上司的上司...一直到Bill
Gates的二级下属升职，由Bill Gates直接管理，因为Steve Ballmer已经是Bill Gates的直接下属了，职位不用变，所以就演变成了下图：
这其实就是并查集的“路径压缩”，在每次搜索到Boss的时候，把路径上所有的节点都直接接到Boss的下面，这样以后再搜索Worker2就省时间啦。
看到这里相信大家已经对并查集有所了解，下面我就用程序模拟上述过程。
先配个数字的转换图方便大家对照：
代码清单：
public class Qinqi {
static int[][] _relative = {
{ 1, 2 }, //1是2的上司
{ 2, 3 },
{ 3, 4 },
{ 5, 6 },
{ 6, 7 },
{ 5, 7 }
};
static final int N = 10;
static int[] _set = new int[N];//并查集
private void initialize() {//初始化
for (int i = 0; i < _set.length; i++) {
_set[i] = i; //每个员工的老板都是自己
}
for (int i = 0; i < _relative.length; i++) {
int high_level = _relative[i][0];//两人中的上司
int low_level = _relative[i][1];//两人中的下属
_set[low_level] = high_level;//确立两人关系
}
}
int findBoss(int worker) {//找到worker的老板
int boss = worker;
while (_set[boss] != boss)//如果worker不是老板就找上司知道找到Boss
boss = _set[boss];
while (worker != boss) {//给worker升职，有Boss直接管理
int high_level = _set[worker];//记录下worker的直接上司
_set[worker] = boss;//把worker的上司设置为boss
worker = high_level;//把他的上司设置为worker
}
return boss;
}
/*判断两个职工是否在同一个公司*/
public boolean isTheSameCompany(int a_worker, int b_worker) {
int a_boss = findBoss(a_worker);
int b_boss = findBoss(b_worker);
return a_boss == b_boss;//老板一样就是一个公司
}
/*a公司收购b公司，由两个员工发起*/
public void buyCompany(int a_worker, int b_worker) {
int a_boss = findBoss(a_worker);
int b_boss = findBoss(b_worker);
if (a_boss == b_boss) {
System.out.println("俩员工在同一公司，不用收购");
return;
}
_set[b_boss] = a_boss;//把b公司的老板的直接上司设置为a公司的老板
}
public static void main(String[] args) {
Qinqi _robot = new Qinqi();
_robot.initialize();//初始化set
_robot.findBoss(3);//找到3的Boss
_robot.buyCompany(3, 6);//worker2和worker3谈收购
}
}
最后收购结果应该是这样：
总之：并查集是判断或维护图的连通性的数据结构。
==================================================================================================
作者：nash_ 欢迎转载，与人分享是进步的源泉！
转载请保留原文地址：http://blog.csdn.net/nash_/article/details/8252925
===================================================================================================