什么是并查集（Union Find）？
并查集是一种孩子指向父亲的特殊树结构
通常用来解决连接问题，
如：网络（抽象）中节点间的连接状态、数学中集合类的实现
并查集所需方法接口
/**
* 并查集接口类
*/
public interface UF {
int getSize();
//查询2个元素是否相互链接
boolean isConnected(int p, int q);
//将2个元素并在一起（相互链接）
void UnionElements(int p, int q);
}
并查集里的数据表示
并查集Quick Find实现方式
因为索引对应的集合若相等则取出，
可相应地得到Quick Find的时间复杂度为O（1）
public class UnionFind1 implements UF{
private int[] id;//数组存储索引
public UnionFind1(int size){
id = new int[size];
for (int i = 0 ; i < id.length ; i ++){
id[i] = i;
}
}
@Override
public int getSize() {
return id.length;
}
//查找元素p所对应的集合编号
private int find(int p){
return id[p];
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
}
Quick Find下的Union操作
如图所示，若想让
1和4两个索引互相连接，则1和4所对应索引的值应该相等，
并且所对应的连接集合也必须相等
得到下图
时间复杂度为O（n）
@Override
public void UnionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if(pID == qID){
return;
}
for (int i = 0 ; i < id.length; i ++){
if(id[i] == pID){
id[i] = qID;
}
}
}
并查集Quick Union实现方式(并查集的真正实现)
这种实现方式将会使子节点指向父节点，
父节点指向自身
1
与Quick Find方法不同
它的每个Id一开始是对应自身，当连接了之后才会改变值
而且为避免树状结构退化成一个链表结构，
我们一般会让一个已经有指向的子节点的父节点去连接所要连接的节点
要想让连接6，2两个元素，则
如上图所示，指向子节点的父节点就行了。
/**
* Created by 53548 on 2019/8/24.
*/
public class UnionFind2 implements UF {
private int [] parent;
public UnionFind2(int size){
parent = new int[size];
for (int i = 0 ; i < size ; i++){
parent[i] = i;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找元素p所对应的集合编号
//时间复杂度为树高度O（h）
private int find(int p){
while(p != parent[p]){
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void UnionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot){
return;
}
parent[pRoot] = qRoot;
}
}
基于size优化并查集
并查集Quick Union虽然能将元素拼接成一颗树，
但由于我们了解的，当一颗树退化成链表结构时，
时间复杂度将会变为O（n）
如：
利用
UnionElements方法Union（0，2）时，将会变成
以此类推，这样实现的并查集的高度会影响到效率。
所以可以进行优化，将节点个数少的树去指向节点个数多的树
如：
从而避免退化成链表
public class UnionFind3 implements UF {
private int [] parent;
private int[] sz; //sz[i]代表集合i的元素的节点个数
public UnionFind3(int size){
parent = new int[size];
sz = new int[size];
for (int i = 0 ; i < size ; i++){
parent[i] = i;
sz[i] = i;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找元素p所对应的集合编号
//时间复杂度为树高度O（h）
private int find(int p){
while(p != parent[p]){
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void UnionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot){
return;
}
if (sz[pRoot] < sz[qRoot]){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else {
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}
基于rank优化并查集
如图所示，基于size的优化有时候并不是最优选，
根为8的集合节点数虽然少于根为7的集合节点数，
但指向后却使树的高度达到了4
而根为7的集合指向8，高度为3，小于size方式的4
/**
* Created by 53548 on 2019/8/24.
*/
public class UnionFind4 implements UF {
private int [] parent;
private int[] rank; //rank[i]代表集合i的元素层数
public UnionFind4(int size){
parent = new int[size];
rank = new int[size];
for (int i = 0 ; i < size ; i++){
parent[i] = i;
rank[i] = i;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找元素p所对应的集合编号
//时间复杂度为树高度O（h）
private int find(int p){
while(p != parent[p]){
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void UnionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot){
return;
}
// 将rank低的合并到rank高的集合
if (rank[pRoot] < rank[qRoot]){
parent[pRoot] = qRoot;
}
else if (rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else {//rank[qRoot] == rank[pRoot]
parent[qRoot] = pRoot;
rank[pRoot] += 1;
}
}
}
并查集路径压缩
让一颗比较高的树压缩成一颗比较矮的树
parent[p] = parent[parent[p]];不断更换父节点，指向父节点的父节点
这样不断切换指向，使得树的高度不断降低，直到指向的根节点无父亲节点
实现一：（只需修改find方法）
//查找元素p所对应的集合编号
//时间复杂度为树高度O（h）
private int find(int p){
while(p != parent[p]){
//路径压缩
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
实现二：
让所有节点指向根节点，实现高度为2的并查集
//查找元素p所对应的集合编号
//时间复杂度为树高度O（h）
private int find(int p){
if(p != parent[p]){
parent[p] = find(parent[p]);
}
return parent[p];
}
