并查集快速合并

骑猪看日落 2024-03-16 23:18 54阅读 0赞

对于一组数据，并查集主要支持两个动作：

*  union(p,q) - 将 p 和 q 两个元素连接起来。
 *  find(p) - 查询 p 元素在哪个集合中。
 *  isConnected(p,q) - 查看 p 和 q 两个元素是否相连接在一起。

在上一小节中，我们用 **id** 数组的形式表示并查集，实际操作过程中查找的时间复杂度为 **O(1)**，但连接效率并不高。

本小节，我们将用另外一种方式实现并查集。把每一个元素，看做是一个节点并且指向自己的父节点，根节点指向自己。如下图所示，节点 3 指向节点 2，代表 3 和 2 是连接在一起的，节点2本身是根节点，所以指向自己。

![de7d8d8881da320a92c0d9fb06afba53.png][]

同样用数组表示并查集，但是下面一组元素用 **parent** 表示当前元素指向的父节点，每个元素指向自己，都是独立的。

![a84a81ea61487e7d5bbf61a5b8828dc1.png][]

![8201d254bce325f0349b5436079447db.png][]

如果此时操作 union(4,3)，将元素 4 指向元素 3：

![1100b0871fc3a1a4ef2a4a96b6509dfd.png][]

数组也进行相应改变：

![dde7d98a2c3ba8909fe7c11cce5c4858.png][]

判断两个元素是否连接，只需要判断根节点是否相同即可。

如下图，节点 4 和节点 9 的根节点都是 8，所以它们是相连的。

![3aef6d63ce992f0bac728b67c3452621.png][]

连接两个元素，只需要找到它们对应的根节点，使根节点相连，那它们就是相连的节点。

假设要使上图中的 6 和 4 相连，只需要把 6 的根节点 5 指向 4 的根节点 8 即可。

![bc4d171faa2c43570a9223b0603423ae.png][]

构建这种指向父节点的树形结构， 使用一个数组构建一棵指向父节点的树，parent\[i\] 表示 i 元素所指向的父节点。

> ...  
> private int\[\] parent;  
> private int count; // 数据个数  
> ...

查找过程, 查找元素 p 所对应的集合编号，不断去查询自己的父亲节点, 直到到达根节点，根节点的特点 parent\[p\] == p，O(h) 复杂度, h 为树的高度。

> ...  
> private int find(int p)\{  
> assert( p >= 0 && p < count );  
> while( p != parent\[p\] )  
> p = parent\[p\];  
> return p;  
> \}  
> ...

合并元素 p 和元素 q 所属的集合，分别查询两个元素的根节点，使其中一个根节点指向另外一个根节点，两个集合就合并了。这个操作是 O(h) 的时间复杂度，h 为树的高度。

> public void unionElements(int p, int q)\{  
> int pRoot = find(p);  
> int qRoot = find(q);  
> if( pRoot == qRoot )  
> return;  
> parent\[pRoot\] = qRoot;  
> \}

#### Java 实例代码 ####

### UnionFind2.java 文件代码： ###

> package runoob.union;  
> /\*\*  
> \* 第二版unionFind  
> \*/  
> public class UnionFind2 \{  
> // 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树  
> // parent\[i\]表示第一个元素所指向的父节点  
> private int\[\] parent;  
> private int count; // 数据个数  
> // 构造函数  
> public UnionFind2(int count)\{  
> parent = new int\[count\];  
> this.count = count;  
> // 初始化, 每一个parent\[i\]指向自己, 表示每一个元素自己自成一个集合  
> for( int i = 0 ; i < count ; i ++ )  
> parent\[i\] = i;  
> \}  
> // 查找过程, 查找元素p所对应的集合编号  
> // O(h)复杂度, h为树的高度  
> private int find(int p)\{  
> assert( p >= 0 && p < count );  
> // 不断去查询自己的父亲节点, 直到到达根节点  
> // 根节点的特点: parent\[p\] == p  
> while( p != parent\[p\] )  
> p = parent\[p\];  
> return p;  
> \}  
> // 查看元素p和元素q是否所属一个集合  
> // O(h)复杂度, h为树的高度  
> public boolean isConnected( int p , int q )\{  
> return find(p) == find(q);  
> \}  
> // 合并元素p和元素q所属的集合  
> // O(h)复杂度, h为树的高度  
> public void unionElements(int p, int q)\{  
> int pRoot = find(p);  
> int qRoot = find(q);  
> if( pRoot == qRoot )  
> return;  
> parent\[pRoot\] = qRoot;  
> \}  
> \}

[de7d8d8881da320a92c0d9fb06afba53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2ed2f4b9466c496eb8ce4a15e795e09b.png
[a84a81ea61487e7d5bbf61a5b8828dc1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d1a9f383cfe9474ca2a96b7e515e74c6.png
[8201d254bce325f0349b5436079447db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/76b0b07b69ab44f4bbddd53dae3e04fc.png
[1100b0871fc3a1a4ef2a4a96b6509dfd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/816ef92bd6274e34ad8978be060e39ad.png
[dde7d98a2c3ba8909fe7c11cce5c4858.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4c1da49d5af54049bbf75038402aa460.png
[3aef6d63ce992f0bac728b67c3452621.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7770ccfe158347d984bb6b5183ac1096.png
[bc4d171faa2c43570a9223b0603423ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7dc54eb2b20c4136aa6466301956273e.png