CS61B：并查集（不相交集）及其简单实现（一）-662P.COM

1：什么是并查集？

所谓并查集，就是没有共同元素的多个集合。比如有如下几个集合：

A：{1，11，21}；B：{22，45，18}；C：{31，91，81}；D：{22，11，81}
A ∩ B=空集，所以A和B是并查集；
A ∩ C=空集，所以A和C也是并查集；
B ∩ C=空集，所以B和C也是并查集；
A ∩ D={11}，有共同元素11，那A和D就不是并查集，同理B和D，C和D。

2：并查集的应用场景有哪些？

根据1中的定义，其实不难看出，并查集的应用，主要是用来根据某些特征对元素（数据）进行分类和归属判断。
这里的元素，可以是城市个体、可以是家族里的个体、基因里的某个片段、甚至是犯罪团伙中的一个小卡拉米。

举1个例子：

例1：A市出现了频繁的盗窃案件。我作为JC蜀黍通过各种观察，目前确认了10名犯罪嫌疑人。在案件初期，我们并不知道这10名犯罪分子，是一个团伙里的，还是隶属于多个团伙。于是乎，我办公室的小黑板上，只能先把名字给列上，用编号表示就是:
1，2，3，4，5，6，7，8，9，10

在这个阶段，由于缺乏证据，我只能推断，他们是单兵作战的，于是我可以把他们单独作为一个集合，即：
{1}，{2}，{3} ...... {10}；

随着对案件调查的深入，我以及我的同事们，有了如下惊人发现：

嫌犯1和嫌犯2是一伙的；{1，2}
嫌犯4和嫌犯7是远房亲戚；{4，7}
嫌犯2和嫌犯9以前踩缝纫机的时候，在同一个号子里蹲过，我们此时又可以通过2把9和1联系起来；{1，2，3}
嫌犯3和嫌犯10来自同一个镇下的两个村，这两个村相距三公里；{3，10}
嫌犯5和嫌犯6，嫌犯8某天一起吃饭；{5，6，8}

以上，我捋清了10个嫌犯的关系，那么现在我们要做的就是根据这些条件确定到底有几个团伙！
由此，我们不同组分别得出了如下的结论：
{1，2，9}，{4，7}，{3，10}，{5，6，8}

继续深入调查，冒出的嫌疑人，越来越多，关系越来越复杂，小黑屋的小黑板，已经完全写不下了，于是我决定用计算机知识，来管理这些嫌疑人的关系。于是又引发出了一个新问题，我TM该怎么管理这些人的关系？于是并查集的基操出现了！

3：并查集的基操有哪些？

我在2中，捋清了犯罪分子的关系。如果有的新的犯罪嫌疑人出现在视线中，我该做什么？
比如我在盯1号的同时，嫌疑人11号出现了，我从没见过11号，我要做的就是：

和其他组交叉对比，确认11号是否已经记录在案；
确认11号所隶属的犯罪团伙；

于是，在此，引出了并查集最主要的操作：

判断11号是否已经被其他组记录，很显然没有；【 isConnect(others, 11) 】
我盯的是1号，11号和1号出现，很显然是和1号一伙的，那么我要做的就是把1号和11号关联起来；【 connect(1,11) 】

至此，我们引出了并查集的两个方法：void connect(T1,T2) 和 boolean isConnect(T1,T2);

4：让我们用计算机语言构建上述模型！

嫌疑犯档案

public class Criminal {  
  
private int number;  
private String name;  
  
private int age;  
  
private String gender;  
  
private String crimeDes;  
  
public int getNumber() {  
return number;  
}  
  
public void setNumber(int number) {  
this.number = number;  
}  
  
public String getName() {  
return name;  
}  
  
public void setName(String name) {  
this.name = name;  
}  
  
public int getAge() {  
return age;  
}  
  
public void setAge(int age) {  
this.age = age;  
}  
  
public String getGender() {  
return gender;  
}  
  
public void setGender(String gender) {  
this.gender = gender;  
}  
  
public String getCrimeDes() {  
return crimeDes;  
}  
  
public void setCrimeDes(String crimeDes) {  
this.crimeDes = crimeDes;  
}

@Override  
public String toString () {  
return "嫌疑人编号: " + this.number + "\t嫌疑人姓名:"+this.name + "\t嫌疑人性别:"+this.gender  
+"\t嫌疑人年龄:" + this.age + "\t嫌疑人涉嫌罪行: "+ this.crimeDes;  
}
}

构建模型：开始只确认了10名嫌犯。

public class CriminalDisJointSetCase {  
  
  
private final int[] criminalNumbers;  
private final Set<Integer> criminalGroupNumbers = new HashSet<>();
  
public CriminalDisJointSetCase(int discoveredCriminalNumbers) {  
//我们知道，嫌疑人肯定不只discoveredCriminalNumbers个人，
所以不妨用大一点的数组来存储嫌疑人的编号；  
criminalNumbers = new int[discoveredCriminalNumbers * 2];  
for (int i = 0; i < discoveredCriminalNumbers; i++) {  
criminalNumbers[i] = i;  
}  
}  

public void connect(int numberOfSuspectA, int numberOfSuspectB) {  
this.criminalNumbers[numberOfSuspectB] = this.criminalNumbers[numberOfSuspectA];  
this.criminalGroupNumbers.add(this.criminalNumbers[numberOfSuspectB]);
}  
  
  
public boolean isConnected(int numberOfSuspectA, int numberOfSuspectB) {  
return this.criminalNumbers[numberOfSuspectA] == this.criminalNumbers[numberOfSuspectB];  
}  
  
public int[] getCriminalNumbers() {  
return this.criminalNumbers;  
}
  
}

构建嫌疑人关系网

public class DisJointSetLauncher {  
  
public static void main(String[] args) {  
  
Criminal[] criminals = new Criminal[20];  
  
//一开始只发现了10名嫌疑人  
for (int i = 0; i < criminals.length ; i++) {  
Criminal criminal = new Criminal();  
criminal.setNumber(i);  
criminal.setAge(new Random().nextInt(18,40));  
criminal.setGender("Male");  
criminal.setName("Thief-"+i);  
criminal.setCrimeDes("入室盗窃");  
criminals[i] = criminal;  
}  
  
//开始为嫌疑人之间建立关系网  
CriminalDisJointSetCase criminalDisJointSetCase = new CriminalDisJointSetCase(10);  
  
//原始关系网  
//expected: 0~9，-1 ...... -1  
//Arrays.stream
(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);  
  
//判断嫌疑人1和2是否是同一个团伙的  
//一开始的时候，没有发现，所以这里应该返回false  
System.out.println();  
System.out.println(criminalDisJointSetCase.isConnected(1,2));  
  
/**  
* 特征1：经过数日侦察，发现嫌疑人1和2一起分赃，于是我们把嫌疑人归并到同一个团伙中去  
*/  
  
  
criminalDisJointSetCase.connect(criminals[1].getNumber(),criminals[2].getNumber());  
  
//此时，嫌疑人1和2，他们的数组值，应该是相等的  
//即，输出结果应该是：-1，1，1，3，4....9，-1, ...... -1  
//由于我们把2的团伙编号，用嫌疑犯1的number替换，所以我们称之为Thief-1团伙  
//Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach
(System.out::print);  
  
//此时我们再判断1和2是否是一个团伙中的: expect: true  
System.out.println();  
System.out.println(criminalDisJointSetCase.isConnected
(criminals[1].getNumber(),criminals[2].getNumber()));  
  
/**  
* 特征2：经过对比户口，嫌疑犯4和嫌疑犯7是远房亲戚，于是我们把4和7归并到同一个团伙中去  
*/  
//false  
System.out.println(criminalDisJointSetCase.isConnected(criminals[4].getNumber(),
criminals[7].getNumber()));  
criminalDisJointSetCase.connect(criminals[4].getNumber(),criminals[7].getNumber());  
//输出结果应该是：-1，1，1，3，4,5,6,4,8,9，-1, ...... -1  
//Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).
boxed().forEach(System.out::print);  
//true  
System.out.println();  
System.out.println(criminalDisJointSetCase.isConnected
(criminals[1].getNumber(),criminals[2].getNumber()));  
  
/**  
* 特征3：嫌犯2和嫌犯9以前踩缝纫机的时候，在同一个号子里蹲过，我们此时又可以通过2把9和1联系起来  
*/  
  
//false  
System.out.println(criminalDisJointSetCase.isConnected
(criminals[1].getNumber(),criminals[9].getNumber()));  
  
criminalDisJointSetCase.connect(criminals[2].getNumber(),criminals[9].getNumber());  
//输出结果应该是：-1，1，1，3，4,5,6,4,8,1......  
//Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach
(System.out::print);  
//true  
System.out.println();  
System.out.println(criminalDisJointSetCase.isConnected
(criminals[1].getNumber(),criminals[9].getNumber()));  
  
/**  
* 特征4：嫌犯3和嫌犯10来自同一个镇下的两个村，这两个村相距三公里  
*/  
System.out.println(criminalDisJointSetCase.isConnected
(criminals[3].getNumber(),criminals[10].getNumber()));  
  
criminalDisJointSetCase.connect(criminals[3].getNumber(),criminals[10].getNumber());  
//输出结果应该是：-1，1，1，3，4,5,6,4,8,1，3，-1....  
Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);  
//true  
System.out.println();  
System.out.println(criminalDisJointSetCase.isConnected
(criminals[3].getNumber(),criminals[10].getNumber()));  
  
/**  
* 特征5：嫌犯5和嫌犯6，嫌犯8某天一起吃饭  
*/  
  
System.out.println(criminalDisJointSetCase.isConnected
(criminals[5].getNumber(),criminals[6].getNumber()));  
  
criminalDisJointSetCase.connect(criminals[5].getNumber(),criminals[6].getNumber());  
criminalDisJointSetCase.connect(criminals[6].getNumber(),criminals[8].getNumber());  
//输出结果应该是：-1，1，1，3，4,5,5,4,5,1，3，-1....  
Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);  
//true  
System.out.println();  
System.out.println(criminalDisJointSetCase.isConnected
(criminals[5].getNumber(),criminals[8].getNumber()));  
  
//此时，团伙编号为：1，3，4，5  
System.out.println(criminalDisJointSetCase.discoveredCriminalGroupNumbers());  
//对应的团伙成员为：  
for (Integer currentNumber : criminalDisJointSetCase.discoveredCriminalGroupNumbers()) {  
System.out.println("当前的团伙编号：" + currentNumber);  
System.out.println("当前的团伙成员为： ");  
for (int i = 1; i <= 10; i++) {  
if (criminalDisJointSetCase.getCriminalNumbers()[i] == currentNumber) {  
System.out.println(criminals[i].toString());  
}  
}  
System.out.println("============================================================");  
}  
}  
}

5：并查集合并规则（谁合并谁？谁被合并？）

在上述侦查中，我们目前构建的犯罪嫌疑人关系网络为：
1号犯罪集团 {1，2，9}；
3号犯罪集团 {3，10}；
4号犯罪集团 {4，7}；
5号犯罪集团 {5，6，8}；

此时，由于3号和4号犯罪集团，在人数上对比1号和5号不占优势，为了能在盗窃事业路上更进一步，决定合并。
问题来了，3号和4号要合并，谁来做老大？嫌疑人3还是嫌疑人4？
在现实案例中，当然要么3和4干一架，要么就3和4比账户余额，要么就比人多。什么想搞双坐馆？下次钓鱼记得带头盔！
而在计算机世界里，就比较简单粗暴了，这里咱们采用靠左原则。所以当3号和4号两个团伙合并的时候，当然3号当大哥了。

public void connect(int numberOfSuspectA, int numberOfSuspectB) {  
this.criminalNumbers[numberOfSuspectB] = this.criminalNumbers[numberOfSuspectA];  
this.criminalGroupNumbers.add(this.criminalNumbers[numberOfSuspectB]);
}

于是我们调用上述写好的方法：connect(3,4);

此时，4的老大就变成3了，而7的老大，还是4。那么问题来了，如果新调来的老李，在熟悉案件过程中，他随机抽到了嫌疑人7的档案，然后他想要找7的老大是谁，只能先按图索骥，找到4，再顺藤摸瓜摸到最终boss 3号。都已经合并了，为什么不直接把7的老大直接设置为3呢？所以上述代码需要改动一下：

public void connect(int numberOfSuspectA, int numberOfSuspectB) {  
int suspectBGangNumber = this.criminalNumbers[numberOfSuspectB];  
this.criminalNumbers[numberOfSuspectB] = this.criminalNumbers[numberOfSuspectA];  
this.criminalGroupNumbers.add(this.criminalNumbers[numberOfSuspectB]);  
for (int i = 0; i < this.criminalNumbers.length; i++) {  
if (this.criminalNumbers[i] == suspectBGangNumber) {  
this.criminalNumbers[i] = this.criminalNumbers[numberOfSuspectB];  
}  
}  
}

6：总结

我们在上述例子中，不断提到成员，归并的时候，不断提到老大，一个团伙只允许有一个老大。在现实中，这种层级结构，是不是特别像计算机中的树形结构？
老大==根节点
成员==子节点
如果你现在去google并查集的真正定义，你会发现这么一段话：

"并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。"

当然，我们在这个盗窃团伙例子中，合并3和4团伙操作的时候，只是简单的遍历更改了一下数组的对应值，就可以让7直接面对合并后的上级3号。

而在实际的应用中，我们所面对的规模，会远比这10个元素庞大的多，比如100W的数据规模，上亿的数据规模。

在connect方法实现中，我们是通过遍历的方式去修改7的父节点，如果这个7，在百万规模的数据中，排在了最后一位（最坏的情况），我们将要遍历100W次，才能修改。这使得connect的时间复杂度为O(N)，这完全是不可以接受的。

后续我们将会一起学习更加合理的数据结构设计以及更加优秀的算法——路径压缩！