并查集
并查集被认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
- 合并（Union）：把两个不相交的集合合并为一个集合。
- 查询（Find）：查询两个元素是否在同一个集合中。
Quick Find
第一个版本的并查集
public interface UnionFind { boolean isConnected(int p,int q); void unionElements(int p ,int q); int getSize(); }
public class UnionFind1 implements UnionFind { private int[] id; public UnionFind1(int size) { id = new int[size]; for (int i = 0; i < id.length; i++) { id[i] = i; } } //查看元素p和元素q是否属于一个集合 @Override public boolean isConnected(int p, int q) { return find(p) == find(q); } //合并元素p和元素q所属的集合 @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; } } } @Override public int getSize() { return id.length; } // 查找元素p所对应的集合编号 private int find(int p) { if (p < 0 || p >= id.length) { throw new IllegalArgumentException("p is out of bound."); } return id[p]; } }
| 操作 | 时间复杂度 |
| unionElements(p,q) | O(n) |
| isConnected(p,q) | O(1) |
Quick Union
我们可以将每一个元素都看作是一个节点。
如果节点3想要连接节点2，那就是节点3去连接节点2，而2又指向自己
如果节点1想要连接节点3也是需要连接节点2即可。如果另一个节点的7想要连接2也是需要当前节点的根节点去连接2即可。
一开始的时候使用数组表示，每一个节点都是根节点和其他节点无关联。
如果我们想union 4，3 节点，我们只需要让4指向3即可。
如果想union3，8其实也非常简单，只需要用3指向8的节点
如果想union9，4其实并不是指向4这个节点，而是指向4的根节点的8。
public class UnionFind2 implements UnionFind{ private int[] parent; public UnionFind2(int size) { parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } //查看元素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; } @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]){ p = parent[p]; } return p; } }
| 操作 | 时间复杂度 |
| unionElements(p,q) | O(h) |
| isConnected(p,q) | O(h) |
基于Size的优化
如果我们union 0，1 然后 union 0，2 然后 union 0，3这样的话就会产生一定的问题，因为我们没有对合并的元素的树没有做判断，所以会导致我们不断增加树的高度，从而成链表的结构。
如果我们的树是这样子的。
我们想union 4，9的话，我们的树就会变成这个样子。深度就达到了4。
但其实我们可以让9来指向4的根节点也就是8。这样我们的深度就只有3。
public class UnionFind3 implements UnionFind{ private int[] parent; //sz[i] 表示以i为根的集合中元素个数 private int[] sz; public UnionFind3(int size) { parent = new int[size]; sz = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; sz[i] = 1; } } //查看元素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; } if(sz[pRoot] < sz[qRoot]){ parent[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }else{ parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } } @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]){ p = parent[p]; } return p; } }
基于Rank的优化
假设现在有这样一棵树，我们进行union4，2根据size优化我们会把8来指向7。现在深度就变为了4。
但是这样子的话，原本的高度是2一下就变为了4，为了优化其实我们可以将7来指向8。深度就变为了3。我们需要将深度低的指向深度高的树
public class UnionFind4 implements UnionFind{ private int[] parent; //rank[i] 表示以i为根的集合中树的层数 private int[] rank; public UnionFind4(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; rank[i] = 1; } } //查看元素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; } //根据两个元素所在树的rank不同判断合并方向 //将rank低的集合合并到rank高的集合上 if(rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; }else if(rank[qRoot] < rank[pRoot]){ parent[qRoot] = pRoot; }else{ parent[qRoot] = pRoot; rank[pRoot] += 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]){ p = parent[p]; } return p; } }
路径压缩
下图中三种树的操作其实都是一样的，但是左边的深度达到了5，而中间可只有2。我们应该如何进行路径压缩？
这样的一棵树结构下，如果我们进行下面操作
parent[p] = parent[parent[p]];
我们让4节点来指向父节点的父节点，也就变成了下面这样。
然后我们再让4的父节点执行同样操作就会变成这样。
//查找过程，查找元素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]]; p = parent[p]; } return p; }
