什么是union-find算法

union-find，顾名思义就是“并查集”，“并查集算法“”就是实现“合并集合”和“查找元素属于哪个集合”的一种算法，它的操作对象是集合。如果任意几个元素同属于一个集合，我们可以认为这几个元素是相连的，元素也可以被称为触点，这几个元素相连构成了一种等价类，等价类也可以被称为连通分量或简称分量。举个简单的例子，在0~9这十个触点中，假设0触点与3触点是相连的，3触点与4触点是相连的，那么“0-3”和“3-4”就是两个连通分量，而且“0-4”也是一个连通分量，这是一种连通分量的传递性。再举一个例子，“连通图”是指图中任意两点都是连通的，即一点到另外一点总是有路径可达的，那么我们可以说这个连通图只有一个连通分量。

union-find算法的API

public class UF	作用
UF(int N)	以整数标识（0到N-1) 初始化N个触点
void union(int p, int q)	在p和q之间添加一条连接
int find(int p)	p(0到N-1)所在的分量的标识符
boolean connected(int p, int q)	如果p和q存在于同一个分量中则返回TRUE
int count()	连通分量的数量

union-find算法的实现

// Java
public class UF
{
	private int[] id;    //分量id（以触点作为索引）
	private int count;   //分量数量
	public UF(int N)
	{   //初始化分量id数组
		count = N;
		id = new int[N];
		for (int i = 0; i < N; i++)
			id[i] = i;
	}
	public int count()
	{
		return count;
	}
	public int find(int p)
	{
		//算法核心，后面讨论
	}
	public void union(int p, int q)
	{
		//算法核心，后面讨论
	}
}

第一种实现：quick-find算法

讲各种实现算法之前，先搞清楚如何评价算法的好坏，这里我们比较的是数组的访问次数，
为什么是数组呢？因为我们可以使用数组的 index 来代表并查集中的元素（也就是触点），数组 index 上存放的值表示元素所属的集合。
顾名思义，quick-find就是“find”很快（好像是句废话）
在这种算法中，我们保证当且仅当" id[p] = id[q] "时p和q是连通的，也就是说，在同一个分量中的所有触点 i，其对应的id[i]必须全部相等。在第一个简单例子中，我们先输入的“0-3”是一个连通分量了，那么我们就令id[0]=id[3]，再输入“3-4”，那就让id[0]=id[3]=id[4]。

代码实现如下：

// Java
public int find(int p)
{
	return id[p];
}
public void union(int p, int q)
{ // 将p和q归并到相同的分量中
	int pID = find(p);
	int qID = find(q);
	
	// 如果p和q已经在相同的分量之中，则不需要采取任何行动
	if(pID == qID) 
	{
		return;
	}
	
	// 将p的分量重命名为q的名称,来保证在同一个分量中的所有触点在id[]中的值必须全部相同
	for(int i = 0; i < id.length; i++)
	{
		if(id[i] == pID)
		{
			id[i] = qID;
		}
	}
	count--;
}

命题F:在quick-find算法中，每次find()调用只需要访问数组依次，而归并两个分量的union()操作访问数组的次数在(N+3)到(2N+1)之间，所以我们应用quick-find算法来解决动态连通性问题时，如果最终只能得到少数连通分量，那么算法的时间复杂度一般是平方级的。这种算法在处理大型数据时不可行。

第二种实现：quick-union算法

这个算法提高了union()方法的速度。在这个算法中，每个触点i所对应的id[i]元素都是同一个分量中的另一个触点的名称（也可能是它自己，这种触点就是根触点），我们将这种联系称为链接。
find()实现的是返回一个触点链接的根触点。
union()实现统一p和q的根触点。

代码实现如下：

private int find(int p)
{ //返回一个触点链接的根触点
	while(p != id[p]
	{
		p = id[p];
	}
	return p;
}
public void union(int p, int q)
{ // 统一p和q的根触点
	int pRoot = find(p);
	int qRoot = find(q);	
	if(pRoot == qRoot)
	{
		return;
	}
	id[pRoot] = qRoot;
	count--;
}

quick-union算法实际上将每个连通分量构造成一棵树，这个树的每个节点就是触点，每个节点的父亲就是触点所对应的的id[]，根节点就是根触点，最后有几棵树就是有几个连通分量。这个算法大多数情况下比quick-find要快，但是最坏情况仍是平方级的。

第三种实现：加权quick-union算法

这是对quick-union算法的改良，quick-union算法在进行归并两棵树时，不考虑两棵树的大小，总是id[pRoot] = qRoot，所以我们考虑在归并两棵树时，将小树（深度小的树）归并到大树下面。为此，我们引入了sz[ ]数组来存放每个由触点索引的树节点所对应的的分量大小（与树节点的深度类似）。

代码实现如下：

...
private int[] sz;  // (由触点索引的)树节点所对应的的分量大小
...
	sz =new int[N];
	for(int i = 0; i < N; i++)
	{
		sz[i] = 1; //初始时，所有树节点都一样高
	}
...
private int find(int p)
{ //返回一个触点链接的根触点
	while(p != id[p]
	{
		p = id[p];
	}
	return p;
}
public void union(int p, int q)
{ // 统一p和q的根触点
	int i = find(p);
	int j = find(q);	
	if(i == j)
	{
		return;
	}
	//让小树的根节点链接到大树的根节点
	if(sz[i] < sz[j])
	{
		id[i] = j;
		sz[j] += sz[i]; // 如果i小，就让j做i的父亲，那么sz[j] += sz[i]
	}
	else
	{
		id[j] = i;
		sz[i] += sz[j];
	}
	count--;
}

在用加权quick-union算法处理N个触点和M条连接时最多访问cMlgN次，其中c是常数。这是三种算法中唯一可以用于解决大型实际问题的算法。

第四种实现：路径压缩的加权quick-union算法

就是对第三种算法的改进，使得树变成几乎完全扁平化的树。要想实现这个路径压缩，我们只需要为find()添加一个循环，将在路径上遇到的所有节点都直接链接到根节点。

代码实现如下：

private int find(int p)
{ //返回一个触点链接的根触点
	while(p != id[p]
	{
		p = id[p];
	}
	//添加一个循环，将在路径上遇到的所有节点都直接链接到根节点。
	int compressPointer = p;
    while (id[compressPointer] != p) 
    {
        int tmp = id[compressPointer];
        id[compressPointer] = p;
        compressPointer = tmp;
    }
	return p;
}

看不懂？

那就看《算法4》的1.5节，或者看这篇文章链接: link
link这一篇讲得很有趣

（这是我第一次写博客，如果你看到最后了，谢谢你的耐心：)）