1 定义
并查集是一种很不一样的树形结构，由子节点指向父节点。常被用来回答连接问题（Connectivity Problem），比如下图中求左上角的点和右下角的点是否相连，我们难以用肉眼观察出结果，需要借助这样的数据结构来帮助我们解决。
网络是个抽象的概念：
社交软件的用户，购物网站的商品信息，交通系统等等都可以抽象成网络中的节点，所以实际中的很多问题都可以借助这个强大的数据结构来解决。
除了解决连接问题，并查集还是数学中集合这一概念的具体实现，并查集的“并”字其实也是数学集合求并集的概念。
主要支持两个动作：
// 将两个数据合并起来
union(p,q);
// 判断p，q是否相连
isConnected(p,q);
程序框架（接口）如下：
public interface UF { int getSize(); boolean isConnected(int p, int q); void unionElements(int p, int q); }
其中p和q表示id，即数组的索引
2 Quick Find实现
在并查集内部，可以为每一个数据索引 p 或 q 分配一个编号id
判断p，q是否属于同一个集合只需查看对应的id是否相同即可。
我们可以定义一个函数 find(p) 来寻找p所对应的分组，相应的isConnected方法会调用find
这样设计的并查集查询操作的时间复杂度为O(1)，所以被称为quick find
public class UnionFind1 implements UF { private int[] id; // 本质就是一个数组 public UnionFind1(int size) { id = new int[size]; // 初始化, 每一个id[i]指向自己, 没有合并的元素 for (int i = 0; i < size; i++) id[i] = i; } @Override public int getSize(){ return id.length; } // 查找元素p所对应的集合编号 // O(1)复杂度 private int find(int p) { if(p < 0 || p >= id.length) throw new IllegalArgumentException("p is out of bound."); return id[p]; } // 查看元素p和元素q是否所属一个集合 // O(1)复杂度 @Override public boolean isConnected(int p, int q) { return find(p) == find(q); } // 合并元素p和元素q所属的集合 // 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; } }
其中合并方法 unionElements(int p, int q) 需要单独解释一下，还是上面的例子，如果此时要合并1和4，那么意味着1所在的组和4所在的组合并
3 Quick Union
不过我们真实实现并查集时，是将每一个元素看作是一个节点，节点之间形成树，只是这棵树是子节点指向父节点的。
例如一个以2为根节点的树：
如果此时另外的节点1要和3进行合并，需要将节点1指向3的根节点
如果有另外一棵以5为根的树，其中节点7要和节点3合并，那么结果是将节点5指向节点2
在这种情况下我们依然可以用数组来进行存储，因为每一个节点只有一个指针指向别人。定义一个parent数组，parent[i]的值表示i指向的节点。初始形状如下：
此时如果要进行union(4,3)操作
对应数组里的
对应数组里的
对应数组中的
再进行union(9, 4)时，需要进行查找，4的父节点是3，3的父节点是8，8是根节点所以9指向8
时间复杂度：
union过程：O(h)，其中h为树的高度，h << n。相应的查询过程的时间复杂度也是O(h)。
public class UnionFind2 implements UF { // 使用一个数组构建一棵指向父节点的树 // parent[i]表示第一个元素所指向的父节点 private int[] parent; // 构造函数 public UnionFind2(int size){ parent = new int[size]; // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合 for( int i = 0 ; i < size ; i ++ ) parent[i] = i; } @Override public int getSize(){ return parent.length; } // 查找过程, 查找元素p所对应的集合编号 // O(h)复杂度, h为树的高度 private int find(int p){ if(p < 0 || p >= parent.length) throw new IllegalArgumentException("p is out of bound."); // 不断去查询自己的父亲节点, 直到到达根节点 // 根节点的特点: parent[p] == p while(p != parent[p]) p = parent[p]; return p; } // 查看元素p和元素q是否所属一个集合 // O(h)复杂度, h为树的高度 @Override public boolean isConnected( int p , int q ){ return find(p) == find(q); } // 合并元素p和元素q所属的集合 // O(h)复杂度, h为树的高度 @Override public void unionElements(int p, int q){ int pRoot = find(p); int qRoot = find(q); if( pRoot == qRoot ) return; parent[pRoot] = qRoot; } }
之后的代码都基于此来进行优化。
4 基于size的优化
上面的例子中，如果依次执行union(0, 1)，union(0, 2)，union(0, 3)，union(0, 4)...则会退化成一个链表，一个简单的解决方案是考虑当前的树有多少个节点。
假设并查集如下：
如果让8指向9的话，最终会得到一颗深度为4的树，但如果让9指向8只会得到一颗高度为3的树。
定义一个sz数组用于记录以i为根的集合中元素个数，union是将sz小的集合的根节点指向sz大的集合的根节点。
核心代码：
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{ // sz[qRoot] <= sz[pRoot] parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } }
5 基于rank的优化
rank指树的高度。
对于下面这个例子：
基于上面基于size优化的代码，节点数小的树指向节点数大的树，union(4, 2)将使得8指向7，将形成一颗高度为4的树，更加合理的合并方案是将7指向8，深度为3。
所以我们在真正合并时应该用深度代替size来决定谁指向谁。
核心代码：
public void unionElements(int p, int q){ int pRoot = find(p); int qRoot = find(q); if( pRoot == qRoot ) return; // 根据两个元素所在树的rank不同判断合并方向 // 将rank低的集合合并到rank高的集合上 if(rank[pRoot] < rank[qRoot]) parent[pRoot] = qRoot; else if(rank[qRoot] < rank[pRoot]) parent[qRoot] = pRoot; else{ // rank[pRoot] == rank[qRoot] parent[pRoot] = qRoot; rank[qRoot] += 1; // 此时维护rank的值 } }
6 路径压缩
上面的代码还是有可能出现退化成链表的情况
由于树的高度决定并查集的性能，所以可以考虑使用路径压缩来尽力降低树的高度。
路径压缩：
讲一课比较高的树变为比较矮的树。
可以将路径压缩过程设计成执行find操作的时候，在寻找的过程中顺便执行路径压缩。路径压缩可以采用如下的方式：
parent[p] = parent[parent[p]];
即将p的父节点设置为其爷爷节点。
在find(4)时，将4的父节点设为2：
继续向上查找，2的父节点变为0
执行完毕之后树的深度从原先的5降低至现在的3。
核心代码：
private int find(int p){ if (p < 0 || p >= parent.length) throw new IllegalArgumentException("p is out of bound"); while (p != parent[p]){ parent[p] = parent[parent[p]]; // 路径压缩，添加后rank不再表示树的高度的物理意义，但是依然有效 p = parent[p]; } return p; }
至此我们对于并查集的优化完全结束。
完整代码：
/* quick union 基于rank（树的层数）的优化 路径压缩 */ public class UnionFind implements UF{ private int[] parent; private int[] rank; // sz[i]表示以i为根的集合中元素个数 public UnionFind(int size){ parent = new int[size]; rank = new int[size]; for (int i = 0; i < size; i ++){ parent[i] = i; rank[i] = 1; } } @Override public int getSize(){ return parent.length; } // 查找过程，查找p对应的集合编号 // O(h)，h为树高度 private int find(int p){ if (p < 0 || p >= parent.length) throw new IllegalArgumentException("p is out of bound"); while (p != parent[p]){ parent[p] = parent[parent[p]]; // 路径压缩，添加后rank不再表示树的高度的物理意义，但是依然有效 p = parent[p]; } return p; } @Override public boolean isConnected(int p, int q){ return find(p) == find(q); } // 合并过程，合并pq所属的集合 // O(h)，h为树高度 @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; // 高度低的树的根指向高度高的树的根，总的高度不变不用维护rank } else if (rank[qRoot] < rank[pRoot]){ parent[qRoot] = pRoot; } else { // rank[qRoot] == rank[pRoot] parent[qRoot] = pRoot; rank[pRoot] += 1; } } }
