并查集(Union-Find)算法介绍

本文主要介绍解决动态连通性一类问题的一种算法，使用到了一种叫作并查集的数据结构，称为Union-Find。java

更多的信息能够参考Algorithms 一书的Section 1.5，实际上本文也就是基于它的一篇读后感吧。算法

原文中更多的是给出一些结论，我尝试给出一些思路上的过程，即为何要使用这个方法，而不是别的什么方法。我以为这个可能更加有意义一些，相比于记下一些结论。编程

关于动态连通性数组

咱们看一张图来了解一下什么是动态连通性：网络

假设咱们输入了一组整数对，即上图中的(4, 3) (3, 8)等等，每对整数表明这两个points/sites是连通的。那么随着数据的不断输入，整个图的连通性也会发生变化，从上图中能够很清晰的发现这一点。同时，对于已经处于连通状态的points/sites，直接忽略，好比上图中的(8, 9)。数据结构

动态连通性的应用场景：数据结构和算法

• 网络链接判断：

若是每一个pair中的两个整数分别表明一个网络节点，那么该pair就是用来表示这两个节点是须要连通的。那么为全部的pairs创建了动态连通图后，就可以尽量少的减小布线的须要，由于已经连通的两个节点会被直接忽略掉。ui

• 变量名等同性(相似于指针的概念)：

在程序中，能够声明多个引用来指向同一对象，这个时候就能够经过为程序中声明的引用和实际对象创建动态连通图来判断哪些引用其实是指向同一对象。编码

 

对问题建模：spa

在对问题进行建模的时候，咱们应该尽可能想清楚须要解决的问题是什么。由于模型中选择的数据结构和算法显然会根据问题的不一样而不一样，就动态连通性这个场景而言，咱们须要解决的问题多是：

• 给出两个节点，判断它们是否连通，若是连通，不须要给出具体的路径
• 给出两个节点，判断它们是否连通，若是连通，须要给出具体的路径

 

就上面两种问题而言，虽然只有是否可以给出具体路径的区别，可是这个区别致使了选择算法的不一样，本文主要介绍的是第一种状况，即不须要给出具体路径的Union-Find算法，而第二种状况可使用基于DFS的算法。

 

建模思路：

最简单而直观的假设是，对于连通的全部节点，咱们能够认为它们属于一个组，所以不连通的节点必然就属于不一样的组。随着Pair的输入，咱们须要首先判断输入的两个节点是否连通。如何判断呢？按照上面的假设，咱们能够经过判断它们属于的组，而后看看这两个组是否相同，若是相同，那么这两个节点连通，反之不连通。为简单起见，咱们将全部的节点以整数表示，即对N个节点使用0到N-1的整数表示。而在处理输入的Pair以前，每一个节点必然都是孤立的，即他们分属于不一样的组，可使用数组来表示这一层关系，数组的index是节点的整数表示，而相应的值就是该节点的组号了。该数组能够初始化为：

for(int i = 0; i < size; i++)
	id[i] = i;

即对于节点i，它的组号也是i。

 

初始化完毕以后，对该动态连通图有几种可能的操做：

• 查询节点属于的组

数组对应位置的值即为组号

• 判断两个节点是否属于同一个组

分别获得两个节点的组号，而后判断组号是否相等

• 链接两个节点，使之属于同一个组

分别获得两个节点的组号，组号相同时操做结束，不一样时，将其中的一个节点的组号换成另外一个节点的组号

• 获取组的数目

初始化为节点的数目，而后每次成功链接两个节点以后，递减1

API

咱们能够设计相应的API：

注意其中使用整数来表示节点，若是须要使用其余的数据类型表示节点，好比使用字符串，那么能够用哈希表来进行映射，即将String映射成这里须要的Integer类型。

 

分析以上的API，方法connected和union都依赖于find，connected对两个参数调用两次find方法，而union在真正执行union以前也须要判断是否连通，这又是两次调用find方法。所以咱们须要把find方法的实现设计的尽量的高效。因此就有了下面的Quick-Find实现。

Quick-Find 算法：

public class UF
{
	private int[] id; // access to component id (site indexed)
	private int count; // number of components
	public UF(int N)
	{
		// Initialize component id array.
		count = N;
		id = new int[N];
		for (int i = 0; i < N; i++)
			id[i] = i;
	}
	public int count()
	{ return count; }
	public boolean connected(int p, int q)
	{ return find(p) == find(q); }
	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);
		// 若是两个组号相等，直接返回
		if (pID == qID) return;
		// 遍历一次，改变组号使他们属于一个组
		for (int i = 0; i < id.length; i++)
			if (id[i] == pID) id[i] = qID;
		count--;
	}
}

举个例子，好比输入的Pair是(5， 9)，那么首先经过find方法发现它们的组号并不相同，而后在union的时候经过一次遍历，将组号1都改为8。固然，由8改为1也是能够的，保证操做时都使用一种规则就行。

上述代码的find方法十分高效，由于仅仅须要一次数组读取操做就可以找到该节点的组号，可是问题随之而来，对于须要添加新路径的状况，就涉及到对于组号的修改，由于并不能肯定哪些节点的组号须要被修改，所以就必须对整个数组进行遍历，找到须要修改的节点，逐一修改，这一下每次添加新路径带来的复杂度就是线性关系了，若是要添加的新路径的数量是M，节点数量是N，那么最后的时间复杂度就是MN，显然是一个平方阶的复杂度，对于大规模的数据而言，平方阶的算法是存在问题的，这种状况下，每次添加新路径就是“牵一发而动全身”，想要解决这个问题，关键就是要提升union方法的效率，让它再也不须要遍历整个数组。

 

Quick-Union 算法：

考虑一下，为何以上的解法会形成“牵一发而动全身”？由于每一个节点所属的组号都是单独记录，各自为政的，没有将它们以更好的方式组织起来，当涉及到修改的时候，除了逐一通知、修改，别无他法。因此如今的问题就变成了，如何将节点以更好的方式组织起来，组织的方式有不少种，可是最直观的仍是将组号相同的节点组织在一块儿，想一想所学的数据结构，什么样子的数据结构可以将一些节点给组织起来？常见的就是链表，图，树，什么的了。可是哪一种结构对于查找和修改的效率最高？毫无疑问是树，所以考虑如何将节点和组的关系以树的形式表现出来。

 

若是不改变底层数据结构，即不改变使用数组的表示方法的话。能够采用parent-link的方式将节点组织起来，举例而言，id[p]的值就是p节点的父节点的序号，若是p是树根的话，id[p]的值就是p，所以最后通过若干次查找，一个节点老是可以找到它的根节点，即知足id[root] = root的节点也就是组的根节点了，而后就可使用根节点的序号来表示组号。因此在处理一个pair的时候，将首先找到pair中每个节点的组号(即它们所在树的根节点的序号)，若是属于不一样的组的话，就将其中一个根节点的父节点设置为另一个根节点，至关于将一颗独立的树编程另外一颗独立的树的子树。直观的过程以下图所示。可是这个时候又引入了问题。

在实现上，和以前的Quick-Find只有find和union两个方法有所不一样：

private int find(int p)
{ 
	// 寻找p节点所在组的根节点，根节点具备性质id[root] = root
	while (p != id[p]) p = id[p];
	return p;
}
public void union(int p, int q)
{ 
	// Give p and q the same root.
	int pRoot = find(p);
	int qRoot = find(q);
	if (pRoot == qRoot) 
		return;
	id[pRoot] = qRoot;    // 将一颗树(即一个组)变成另一课树(即一个组)的子树
	count--;
}

树这种数据结构容易出现极端状况，由于在建树的过程当中，树的最终形态严重依赖于输入数据自己的性质，好比数据是否排序，是否随机分布等等。好比在输入数据是有序的状况下，构造的BST会退化成一个链表。在咱们这个问题中，也是会出现的极端状况的，以下图所示。

为了克服这个问题，BST能够演变成为红黑树或者AVL树等等。

 

然而，在咱们考虑的这个应用场景中，每对节点之间是不具有可比性的。所以须要想其它的办法。在没有什么思路的时候，多看看相应的代码可能会有一些启发，考虑一下Quick-Union算法中的union方法实现：

public void union(int p, int q)
{ 
	// Give p and q the same root.
	int pRoot = find(p);
	int qRoot = find(q);
	if (pRoot == qRoot) 
		return;
	id[pRoot] = qRoot;  // 将一颗树(即一个组)变成另一课树(即一个组)的子树
	count--;
}

上面 id[pRoot] = qRoot 这行代码看上去彷佛不太对劲。由于这也属于一种“硬编码”，这样实现是基于一个约定，即 p 所在的树老是会被做为 q 所在树的子树，从而实现两颗独立的树的融合。那么这样的约定是否是老是合理的呢？显然不是，好比 p 所在的树的规模比 q 所在的树的规模大的多时， p 和 q 结合以后造成的树就是十分不和谐的一头轻一头重的”畸形树“了。

因此咱们应该考虑树的大小，而后再来决定究竟是调用：

id[pRoot] = qRoot 或者是 id[qRoot] = pRoot

即老是size小的树做为子树和size大的树进行合并。这样就可以尽可能的保持整棵树的平衡。

 

因此如今的问题就变成了：树的大小该如何肯定？

咱们回到最初的情形，即每一个节点最一开始都是属于一个独立的组，经过下面的代码进行初始化：

for (int i = 0; i < N; i++)
	id[i] = i;    // 每一个节点的组号就是该节点的序号

以此类推，在初始状况下，每一个组的大小都是1，由于只含有一个节点，因此咱们可使用额外的一个数组来维护每一个组的大小，对该数组的初始化也很直观：

for (int i = 0; i < N; i++)
	sz[i] = 1;    // 初始状况下，每一个组的大小都是1

而在进行合并的时候，会首先判断待合并的两棵树的大小，而后按照上面图中的思想进行合并，实现代码：

public void union(int p, int 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]; }
	else { id[j] = i; sz[i] += sz[j]; }
	count--;
}

Quick-Union 和 Weighted Quick-Union 的比较：

能够发现，经过sz数组决定如何对两棵树进行合并以后，最后获得的树的高度大幅度减少了。这是十分有意义的，由于在Quick-Union算法中的任何操做，都不可避免的须要调用find方法，而该方法的执行效率依赖于树的高度。树的高度减少了，find方法的效率就增长了，从而也就增长了整个Quick-Union算法的效率。

 

上图其实还能够给咱们一些启示，即对于Quick-Union算法而言，节点组织的理想状况应该是一颗十分扁平的树，全部的孩子节点应该都在height为1的地方，即全部的孩子都直接链接到根节点。这样的组织结构可以保证find操做的最高效率。

 

那么如何构造这种理想结构呢？

在find方法的执行过程当中，不是须要进行一个while循环找到根节点嘛？若是保存全部路过的中间节点到一个数组中，而后在while循环结束以后，将这些中间节点的父节点指向根节点，不就好了么？可是这个方法也有问题，由于find操做的频繁性，会形成频繁生成中间节点数组，相应的分配销毁的时间天然就上升了。那么有没有更好的方法呢？仍是有的，即将节点的父节点指向该节点的爷爷节点，这一点很巧妙，十分方便且有效，至关于在寻找根节点的同时，对路径进行了压缩，使整个树结构扁平化。相应的实现以下，实际上只须要添加一行代码：

private int find(int p)
{
	while (p != id[p])
	{
		// 将p节点的父节点设置为它的爷爷节点
		id[p] = id[id[p]];
		p = id[p];
	}
	return p;
}

至此，动态连通性相关的Union-Find算法基本上就介绍完了，从容易想到的Quick-Find到相对复杂可是更加高效的Quick-Union，而后到对Quick-Union的几项改进，让咱们的算法的效率不断的提升。

这几种算法的时间复杂度以下所示：

 

对大规模数据进行处理，使用平方阶的算法是不合适的，好比简单直观的Quick-Find算法，经过发现问题的更多特色，找到合适的数据结构，而后有针对性的进行改进，获得了Quick-Union算法及其多种改进算法，最终使得算法的复杂度下降到了近乎线性复杂度。

 

若是须要的功能不只仅是检测两个节点是否连通，还须要在连通时获得具体的路径，那么就须要用到别的算法了，好比DFS或者BFS。

并查集的应用，能够参考另一篇文章 并查集应用举例