1：让我们从删除代码开始！
还记得我们在[第一部分](CS61B： 并查集（不相交集）及其简单实现（一） - 掘金 (juejin.cn))中写的connect方法么？
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];
}
}
}
在这个盗窃团伙的例子中，我们在最后合并了两个团伙。在这个规模只有10多个的例子中，为了能更直观的表示上下级关系，我们用一个for循环，把被合并的4号团伙的成员7的上级，由原来的4号更改为了3号。这也直接导致了，时间复杂度，由O(1)暴涨为O(N)。
现在，我不仅想保持isConnected(x,y)的时间复杂度为O(1),我还想降低connect(x,y)的时间复杂度。
没错，我就是想“既要......又要......”。
So，让我们退回到这个最初的版本！
//这是最初的代码，它的时间复杂度就是O(1)
int suspectBGangNumber = this.criminalNumbers[numberOfSuspectB];
this.criminalNumbers[numberOfSuspectB] = this.criminalNumbers[numberOfSuspectA];
this.criminalGroupNumbers.add(this.criminalNumbers[numberOfSuspectB]);
那么此时，数组元素为：
index[1] = 1, index[2]=1,index[3]=3,index[4]=3,index[5]=5,index[6]=5,index[7]=4 ......
我们提到用下标表示团伙成员编号，数组值表示各自的上级，根据上述，我们可以构建这样的树：
此时我们可以想象添加一个find（item）辅助方法，专门用来寻找某个元素的root。
每一次我们要合并，都需要先通过find(item)方法，寻找root，再合并。
同理，每一次判断两个元素是否是在同一个集合，也需要用find(item)方法，寻找root。
而此时我们要找到7的上级，也不过是遍历两层而已。
但是，有没有想过，我们会遇到这样的极端情况：
好家伙，发现没有，这一回退不得了。此时我们不仅没把connect(x,y)的时间复杂度干下来，连isConnected(x,y)都无法幸免了，这完全是不能接受的！
2：加权合并算法——加什么权？？
由于我们引入了一个find(item)辅助函数，不难发现，要降低时间复杂度，其实就是研究要怎么样才能更快爬到根节点。
到了这里，我们理解了，所谓的connect，就是合并两棵树。那怎么合并呢？假设我们现在有如下图两棵树：
有如下两种选择，阁下如何应对？
当然是选择OPTION2了，因为T2的高度是2，且它的元素数量只有3个，更容易上树顶。于是我们引出了如下规则：
小树（数量少，这里是3）被大树（数量大，这里是6）合并！
注意：不是按照高度计算的，而是按照元素数量来确定大小。
而数量，就是这里的权重！
最后，还记得我们在代码中，如何在数组中表示root节点么？如果忘记了，没关系，我们再温习一遍：
如果数组值=数组下标，则代表这个数组值，是一个root。
现在，时代变了大人们！我们要用树的元素数量的相反数，即-(size)，表示树的节点。在上图中，T1、T2在以前的数组中分布情况如下：
T1 EX: index[0] = 0, index[1] = 0, index[2] = 0, index[3] = 0, index[5] = 3 ......;
T1 NOW: index[0] = -6, ...... index[5] = 3;
T2 EX: index[6] = 6, ......;
T2 NOW: index[6] = -3;
最最后，connect和isConnect的时间复杂度都降到了O(logN)。
树的时间复杂度计算方法不再赘述，这里直接给结果
尽管在此前isConnect的时间复杂度为O(1)，但是connect为O(N)，所以这里就要讲究一下折中调和。好事不能全让isConnect占了！
加权合并算法(Weighted Qucik Union)优化下的并查集代码实现!
public class CriminalDisJointSetCase {
//在这个数组中，我们用下标来表示嫌疑人编号，而数组值则表示嫌疑人隶属的团伙人数。
//即 i = 嫌疑人编号（criminal.getNumber）; criminalNumber[i] = 团伙人数；
private final int[] criminalNumbers;
private final List criminalGroupNumbers = new ArrayList();
public CriminalDisJointSetCase(int discoveredCriminalNumbers) {
criminalNumbers = new int[discoveredCriminalNumbers];
//初始化的时候，各自为战，全是-1
Arrays.fill(criminalNumbers,-1);
}
//
public void connect(int numberOfSuspectA, int numberOfSuspectB) {
if (!isConnected(numberOfSuspectA,numberOfSuspectB)) {
int rootA = this.find(numberOfSuspectA);
int rootB = this.find(numberOfSuspectB);
int newNodesNum = Math.abs(this.criminalNumbers[rootA]) + Math.abs(this.criminalNumbers[rootB]);
//Attention root value is negative
if (this.criminalNumbers[rootA] > this.criminalNumbers[rootB]) {
//将rootA的上级设置为rootB
this.criminalNumbers[rootA] = numberOfSuspectB;
//更新节点数
this.criminalNumbers[rootB] = -newNodesNum;
} else {
this.criminalNumbers[rootB] = numberOfSuspectA;
this.criminalNumbers[rootA] = -newNodesNum;
}
}
}
public int find(int criminal) {
int root = this.criminalNumbers[criminal];
if ( root < 0) {
return criminal;
}
return find(root);
}
public boolean isConnected(int numberOfSuspectA, int numberOfSuspectB) {
return find(numberOfSuspectA) == find(numberOfSuspectB);
}
public int[] getCriminalNumbers() {
return this.criminalNumbers;
}
public List discoveredCriminalGroupNumbers() {
this.criminalGroupNumbers.clear();
for (int criminalNumber : this.criminalNumbers) {
if (criminalNumber < 0) {
this.criminalGroupNumbers.add(criminalNumber);
}
}
return this.criminalGroupNumbers;
}
}
public class DisJointSetLauncher {
public static void main(String[] args) {
Criminal[] criminals = new Criminal[10];
//一开始只发现了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: all -1
for (Integer integer : criminalDisJointSetCase.getCriminalNumbers()) {
System.out.printf(integer+"\t");
}
System.out.println();
//判断嫌疑人1和2是否是同一个团伙的
//一开始的时候，没有发现，所以这里应该返回false
System.out.println(criminalDisJointSetCase.isConnected(0,1));
/**
* 特征1：经过数日侦察，发现嫌疑人1和2一起分赃，于是我们把嫌疑人归并到同一个团伙中去
* {criminal 0, criminal 1}
*/
criminalDisJointSetCase.connect(criminals[0].getNumber(),criminals[1].getNumber());
//此时我们再判断嫌疑人1和2是否是一个团伙中的: expect: true
System.out.println(criminalDisJointSetCase.isConnected(criminals[0].getNumber(),criminals[1].getNumber()));
/**
* 特征2：经过对比户口，嫌疑犯3和嫌疑犯6是远房亲戚，于是我们把3和6归并到同一个团伙中去
*
* {criminal 2, criminal 5}
*/
//false
System.out.println(criminalDisJointSetCase.isConnected(criminals[2].getNumber(),criminals[5].getNumber()));
criminalDisJointSetCase.connect(criminals[2].getNumber(),criminals[5].getNumber());
//true
System.out.println(criminalDisJointSetCase.isConnected(criminals[2].getNumber(),criminals[5].getNumber()));
/**
* 特征3：嫌犯1和嫌犯8以前踩缝纫机的时候，在同一个号子里蹲过，我们此时又可以通过1把8和2联系起来
*
* {criminal 0, criminal 1,criminal 7}
*/
//false
System.out.println(criminalDisJointSetCase.isConnected(criminals[0].getNumber(),criminals[7].getNumber()));
criminalDisJointSetCase.connect(criminals[0].getNumber(),criminals[7].getNumber());
//true，true
System.out.println(criminalDisJointSetCase.isConnected(criminals[0].getNumber(),criminals[7].getNumber()));
System.out.println(criminalDisJointSetCase.isConnected(criminals[1].getNumber(),criminals[7].getNumber()));
/**
* 特征4：嫌犯3和嫌犯10来自同一个镇下的两个村，这两个村相距三公里
*
* {criminal 2, criminal 5, criminal 9}
*/
//false
System.out.println(criminalDisJointSetCase.isConnected(criminals[2].getNumber(),criminals[9].getNumber()));
criminalDisJointSetCase.connect(criminals[2].getNumber(),criminals[9].getNumber());
//true
System.out.println(criminalDisJointSetCase.isConnected(criminals[5].getNumber(),criminals[9].getNumber()));
/**
* 特征5：嫌犯5和嫌犯6，嫌犯8某天一起吃饭
*
* {criminal 2,criminal4, criminal 5, criminal 7, criminal 9}
*/
//false
System.out.println(criminalDisJointSetCase.isConnected(criminals[4].getNumber(),criminals[5].getNumber()));
criminalDisJointSetCase.connect(criminals[4].getNumber(),criminals[5].getNumber());
criminalDisJointSetCase.connect(criminals[4].getNumber(),criminals[7].getNumber());
//true
System.out.println(criminalDisJointSetCase.isConnected(criminals[4].getNumber(),criminals[7].getNumber()));
System.out.println(criminalDisJointSetCase.isConnected(criminals[2].getNumber(),criminals[9].getNumber()));
System.out.println(criminalDisJointSetCase.isConnected(criminals[5].getNumber(),criminals[4].getNumber()));
/**
* 此时团伙为：
* {criminal 0, criminal 1, criminal 2,criminal4, criminal 5, criminal 7, criminal 9}
* ,{criminal 3}, {criminal 6} {criminal 8}
*/
System.out.println(criminalDisJointSetCase.discoveredCriminalGroupNumbers());
criminalDisJointSetCase.connect(2,3);
//do nothing
criminalDisJointSetCase.connect(1,5);
//此时，只有criminal 6, 8 是单打独斗了
//expect : -1
System.out.println(criminalDisJointSetCase.getCriminalNumbers()[criminals[6].getNumber()]);
System.out.println(criminalDisJointSetCase.getCriminalNumbers()[criminals[8].getNumber()]);
// expected {-8,-1,-1}
List criminalGroupNumbers= criminalDisJointSetCase.discoveredCriminalGroupNumbers();
criminalDisJointSetCase.connect(6,8);
//expected {-8,-2}
criminalGroupNumbers= criminalDisJointSetCase.discoveredCriminalGroupNumbers();
for (Integer currentNumber : criminalGroupNumbers) {
System.out.println("\n\n当前的团伙编号：" + currentNumber);
System.out.println("当前的团伙成员为： ");
for (Criminal criminal : criminals) {
int boss = criminalDisJointSetCase.find(criminal.getNumber());
if (currentNumber == criminalDisJointSetCase.getCriminalNumbers()[boss]) {
System.out.println(criminal);
}
}
System.out.println("============================================================");
}
}
}
3：总结
Attention：我的代码注释可能存在一些错误，这里我就不纠正了，建议一行行的debug走一遍。
这一次优化，添加了一个辅助函数，find(int item)，作用是找到root节点。
复制粘贴运行后，输出结果如下：
4：What's the next ?
查看如下debug截图，用来保存元素的数组，看上去是不是非常难受？
举个例子：从7为切入点，要找到他的root，要不断递归，7 -> 0 -> 4 -> 5 -> 2,才能找到root节点？那我们可不可以，直接把7设置成4，或者5，或者直接让7面对root 2 ？ 当然可以！
这就是路径压缩！在我发下一篇文章的时候，大家不妨自己先去了解一下，尝试着自己把代码实现了！
