Uion-Find 算法
在计算机科学中，
并查集
（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
-
查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
-
-
添加
：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。
由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。
并查集是用于计算最小生成树的
迪杰斯特拉算法
中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。
引论
设计一个算法大致分为六个步骤：
-
-
设计一个算法来解决问题（Find an algorithm to solve it）
-
判断算法是否足够高效？（Fast Enough?)
-
如果不够高效，思考为什么，并进行优化。（If not，figure out why ?）
-
寻找一种方式来处理问题 (Find a way to address the problem)
-
迭代设计，直到满足条件 (Iterate until satisfied.)
我们从一个基本问题：网络连通性（Network connectivity）出发，该问题可以抽象为：
-
-
-
FIND 查询：是否有路径将一个对象连接到另一个对象？
并查集的对象可以是下面列出的任何类型：
图 1 连通图
在编程的时候，为了方便起见，我们对这些对象从 0 到 n-1 进行编号，从而用一个整形数字表示对象。隐藏与 Union-find 不相关的细节；可以使用整数快速获取与对象相关的信息（数组的下标）；可以使用符号表对对象进行转化。
简化有助于我们理解连通性的本质。
如图 1 所示，假设我们有编号为
[0,1,2,3,4,5,6,7,8,9]
的 10 个对象，对象的不相交集合为 :
{{0},{1},{2,3,9},{5,6},{7},{4,8}}
。
Find
查询：2 和 9 是否在一个集合当中呢？
答：
{{0},{1},{
2
,3,
9
},{5,6},{7},{4,8}}
。
Union
命令：合并包含 3 和 8 的集合。
答：
{{0},{1},{2,
3
,4,
8
,9},{5,6},{7}}
。
连接组件(Connected Component)：一组相互连接的顶点.
每一次 Union 命令会将组（连通分量）的数量减少 1 个。
如上图所示，初始时，每一个顶点为一个组，我们执行了 7 次 Union 操作后，变成了 3 个组。其中
{2 9}
不算做一次 Union 操作，是因为在 Union 之前，我们使用 Find 查找命令，会发现
{2 9}
此时已经位于同一个组
{2 3 4 5 6 9}
当中。
以网络连通性问题为例，如下图所示，
find(u,v)
可以判断顶点 u 和 v 是否联通？
如下图所示，图中共包含 63 个组，其中对象 u 和 对象 v 在同一个集合当中，我们可以找到一条从对象 u 到对象 v 的路径（红色路线）但是我们并不关心这条路劲本身，只关心他们是否联通：
上面的问题看似很复杂，但也很容易抽象为 Union-Find 模型：
-
-
-
-
Union 命令：将包含两个对象的集合替换为它们的并集。
现在目标就是为 Union-Find 设计一个高效的数据结构：
-
-
Find 和 Union 的操作数量 M 可能很大。
-
Quick-Find
设计一个大小为 N 的整型数组
id[]
，如果 p 和 q 有相同的
id
，即
id[p] = id[q]
，则认为 p 和 q 是联通的，位于同一个集合中，如下图所示，5 和 6 是联通的，2、3、4 和 9 是联通的。
Find(p,q)
查询操作只需要判断 p 和 q 是否具有相同的 id，即
id[p]
是否等于
id[q]
；比如查询
Find(2,9)
，
id[2] = id[9] = 9
，则 2 和 9 是联通的。
Union(p,q)
操作：合并包含 p 和 q 的所有组，将输入中所有 id 为
id[p]
的对象 id 修改为
id[q]
。比如
Union(3,6)
，需要将 id 为
id[3] = 9
的所有对象
{2,3,4,9}
的 id 均修改为
id[6] = 6
，如下图所示。
Find(u,v)
的时间复杂度为
，
Union(p,q)
的时间复杂度为
量级 ，每一次
Union
操作需要更新很多元素
i
的 index
id[i]
。
以下图为例，我们依次执行
Union(3,4)
，
Union(4,9)
，
Union(8,0)
，
Union(2,3)
，......，
Union(6,1)
操作，整形数组
id[]
中元素的变化过程。
实现
public class QuickFind
{
private int[] id;
public QuickFind(int N)
{
id = new int[N];
for (int i = 0; i id[i] = i;
}
}
public boolean find(int p, int q)
{
return id[p] == id[q];
}
public void unite(int p, int q)
{
int pid = id[p];
for (int i = 0; i if (id[i] == pid) {
id[i] = id[q];
}
}
}
}
复杂度分析
Quick-find 算法的
find
函数非常简单，只是判断
id[p] == id[q]
并返回，时间复杂度为
，而
Union(u,v)
函数因为无法确定谁的 ID 与
id[q]
相同，所以每次都要把整个数组遍历一遍，如果一共有
个对象，则时间复杂度为
。综合一下，表示如果
Union
操作执行
次，总共
个对象（数组大小），则时间复杂度为
量级，。
因为这个算法
Find
操作很快，而
Union
操作却很慢，所以将其称为
Quick-Find
算法。
Quick-Union
回忆 Quick-Find 中 union 函数，就像是暴力法，遍历所有对象的
id[]
，然后把有着相同
id
的数全部改掉， Quick-Union 算法则是引入 “树” 的概念来优化 union 函数，我们把每一个数的
id
看做是它的父结点。比如说，
id[3] = 4
，就表示 3 的父结点为 4。
与 Quick-Find 算法使用一样的数据结构，但是
id[]
数组具有不同的含义：
-
-
-
i
的根结点为
id[id[id[...id[i]...]]]
如图所示，
id[2] = 9
就表示 2 的父结点为 9；3 的根节点为 9 (3 的父结点为 4，4 的父结点为 9，9的父结点还是 9，也就是根结点了)，5 的根结点为 6 。
那么
Find(p,q)
操作就变成了判断
p
和
q
的根结点是否相同，比如
Find(2,3)
，2 和 3 的根结点 9 相同，所以 2 和 3 是联通的。
Union(p,q)
操作就是将
q
根结点的 id 设置为
p
的根结点的 id。如上图所示，
Union(3,5)
就是将
5
的根结点的
6
设置为
3
的根结点
9
，即
id[5] = 9
，仅更新一个元素的
id
。
对于原数组
i = {0,1,2,3,4,5,6,7,8,9}
及 id 数组
id[10] = {0,1,2,3,4,5,6,7,8,9}
，依次执行
Union(3,4)
，
Union(4,9)
，
Union(8,0)
，
Union(2,3)
，
Union(5,6)
，
Union(5,9)
，
Union(7,3)
，
Union(4,8)
，
Union(6,2)
的过程中如下：
实现代码
public class QuickUnion
{
private int[] id;
public QuickUnion(int N) {
id = new int[N];
for (int i = 0; i }
private int root(int i) {
while (i != id[i]) i = id[i];
return i;
}
public boolean find(int p, int q) {
return root(p) == root(q);
}
public void unite(int p, int q) {
int i = root(p);
int j = root(q);
id[i] = j;
}
}
复杂度分析
对于
Find(p,q)
操作，只需要找到 p 的根结点和 q 的根结点，检查它们是否相等。合并操作就是找到两个根节点并将第一个根节点的 id 记录值设为第二个根节点 。
与 Quick-Find 算法相比， Quick-Union 算法对于问题规模较大时是更加高效。不幸的是，Quick-Union 算法快了一些但是依然太慢了，相对 Quick-Find 的慢，它是另一种慢。有些情况下它可以很快，而有些情况下它还是太慢了。但 Quick-Union 算法依然是用来求解动态连通性问题的一个快速而优雅的设计。
Quick-Union 算法的缺点在于树可能太高了。这意味着查找操作的代价太大了。你可能需要回溯一棵瘦长的树（斜树），每个对象只是指向下一个节点，那么对叶子节点执行一次查找操作，需要回溯整棵树，只进行查找操作就需要花费 N 次数组访问，如果操作次数很多的话这就太慢了。
Find
操作：最好时间复杂度为
，最坏为
，平均
。
Union
操作：最好时间复杂度为
，最坏为
，平均
当进行
次 Union 操作，那么平均时间复杂度就是
。
Weighted Quick-Union
好，我们已经看了快速合并和快速查找算法，两种算法都很容易实现，但是不支持巨大的动态连通性问题。那么，我们该怎么改进呢？
一种非常有效的改进方法，叫做加权。也许我们在学习前面两个算法的时候你已经想到了。这个改进的想法是在实现 Quick-Union 算法的时候执行一些操作避免得到一颗很高的树。
如果一棵大树和一棵小树合并，避免将大树放在小树的下面，就可以一定程度上避免更高的树，这个加权操作实现起来也相对容易。我们可以跟踪每棵树中对象的个数，然后我们通过确保将小树的根节点作为大树的根节点的子节点以维持平衡，所以，我们避免将大树放在小树下面的情况。
如上图所示，以
Union(5,3)
为例，5 的根结点为 6，3 的根结点为 9 ：
-
Quick-Union：以 9 为根结点树将作为 6 的子树
-
Weighted Quick-Union：以 6 为根结点的树将作为 9 的子树。
我们可以看一下 Weighted Quick-Union 操作的例子：
可以看到 Weighted Quick-Union 所生成的树很 “胖”，刚好满足我们的需求。
实现代码
Weighted Quick-Union 的实现基本和 Quick-Union 一样，我们只需要维护一个数组
sz[]
，用来保存以 i 为根的树中的对象个数，比如
sz[0] = 1
，就表示以 0 为根的树包含 1 个对象。
public class WeightedQuickUnion
{
private int[] id;
private int[] sz;
public WeightedQuickUnion(int N) {
id = new int[N];
sz = new int[N];
for (int i = 0; i id[i] = i;
sz[i] = 1; // 初始时，每一个结点为一棵树，sz[i] = 1
}
}
private int root(int i) {
while (i != id[i]) i = id[i];
return i;
}
public boolean find(int p, int q) {
return root(p) == root(q);
}
public void unite(int p, int q) {
int i = root(p);
int j = root(q);
if (sz[i] id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
}
}
复杂度分析
对于加权 Quick-Union 算法处理
个对象和
条连接时最多访问
次，其中
为常数，即时间复杂度为
量级。与 Quick-Find 算法（以及某些情况下的 Quick-Union 算法）的时间复杂度
