树的应用——使用并查集解决动态连通性问题（含C++代码实现）（上篇：快速查找）

动态连通性问题简述

动态连通性问题Dynamic Connectivity Problem
给定一个包含N个对象的集合A, A = { a 1 , a 2 , a 3 , a 4 , … , a n } A={a_1,a_2,a_3,a_4,…,a_n} A={a1​,a2​,a3​,a4​,…,an​} 。
解决以下三个问题：

1. 设计一种算法union()，使 $a_i$ 与 $a_j$ 连通 ($i,j=1,2,3,\dots ,n$)。
   示意图：
   

2. 设计一种数据结构（数据表示法），表示并存储对象与对象之间的连通关系。

3. 设计一种算法isConnected()，用于在上述结构中查询 $a_i$ 与 $a_j$ 之间是否连通（是否存在一条路径使得从 $a_i$ 出发能走到 $a_j$）。若是，返回true，否则返回false。
   示意图：
   

抽象模型

为便于编程，将集合A中的N个对象，从0开始编号，最后一个对象编号为N-1.

从问题1的描述中，可以归纳出，连通具有以下性质：($i,j,k=0,1,2,3,\dots ,n-1$)

1. 自反性：每一个对象都与它本身连通，即 $i$ 与 $i$ 连通
2. 对称性：如果 $i$ 与 $j$ 连通，那么 $j$ 与 $i$ 也连通
3. 传递性：如果 $i$ 与 $j$ 连通，$j$ 与 $k$ 连通，那么 $i$ 与 $k$ 连通

我们可以使用连通分量 （并查集）来表示这种连通关系，例如：

我们将相互连通的对象放在一个集合中，孤立的对象也单独放入一个集合。这样集合A就被划分为了4个红色的小集合，即4个连通分量。每个连通分量内的对象都是相互连通的。所有四个连通分量所构成的集合就是并查集。

函数原型设计

class DynamicConnectivity{
private:
	int N;  //集合A内对象个数
	int* id;  //存储连通关系（和对象）的数据结构
public:
	DynamicConnectivity(int N);  //初始化函数，向Union[]中填入数据
	void Union(int p, int q);	//合并函数，将对象p与q连通的函数
	bool isConnected(int p, int q);   //查找函数，查询对象p与q是否连通的函数
};
1
2
3
4
5
6
7
8
9

算法设计与实现

第一种设计：快速查找 Quick-find

在这种设计中，数据结构id[]是一个整数类型的数组。数组每个元素的索引index是对象的编号，相互连通的对象所对应的数组元素的值value相同。例如：
id[10]=

其对应于连通分量 {0,1,2,5,6,7} 和 {3,4,8,9}

接下来我们将以上述两个连通分量构成的并查集为最终效果，讲解如何实现初始化函数DynamicConnectivity()和Union()，将0~9这10个对象连通成上述情况。

1.DynamicConnectivity(int N)：

根据连通的自反性，初始化时对于尚未构成任何连通关系的这10个孤立的对象，我们可以将它们初始化为自己与自己连通，即：

代码实现：

DynamicConnectivity::DynamicConnectivity(int N)
{
	id = new int[N];
	for (int i = 0; i < N; i++)
		id[i] = i;
}
1
2
3
4
5
6

2.Union(int p,int q):

我们要将对象p与对象q连通，那么根据连通的性质，凡是与对象p连通的对象，在Union(p,q)之后，都与q对象及其连通的对象连通。换句话说，p所在的连通分量，与q所在的连通分量做并运算，形成一个新的连通分量。

首先，我们存储id[p]的值到临时变量int pid中，存储id[q]的值到临时变量int qid中，然后，根据前面数据结构那里约定的表示法，我们遍历数组，凡是值等于pid的元素（即与p对象处在同一连通分量中的对象）的值，都改为qid。最后p，q所在的连通分量的所有对象对应的值都相等，新的连通分量形成了。假设id[]刚刚初始化，然后我们进行三次Union操作:

Union(0,1)

“将id[1]的值赋给了id[0]”

Union(2,1)

“将id[1]的值赋给id[2]”

Union(5,2)

“将id[2]的值赋给id[5]”

Union()的原理讲完，接下来代码实现就很简单了：
代码实现：

void DynamicConnectivity::Union(int p,int q)
{
	int pid = id[p];
	int qid = id[q];
	for (int i = 0; i < N; i++)
		if (id[i] == pid) id[i] = qid;
}
1
2
3
4
5
6
7

经典错误：

void DynamicConnectivity::Union(int p,int q)
{
	for (int i = 0; i < N; i++)
		if (id[i] == id[p]) id[i] = id[q];
}
1
2
3
4
5

3.isConnected(int p, int q)

有了前面的铺垫，这个函数的实现就非常简单了。我们只需查询id[p]的值是否等于id[q]，如果相等，即p对象所对应的数组元素的值等于q，则说明这两个对象处在同一连通分量中。否则，不连通。

代码实现：

bool DynamicConnectivity::isConnected(int p, int q)
{
	return id[p] == id[q];
}
1
2
3
4

算法分析

时间复杂度

从上表，很容易理解为什么该算法叫做快速查找而不是快速合并了。

本算法，最大的时间开销在于合并函数，因为要循环遍历id[]数组。我们考虑最坏的情况，当有N个对象而我们要执行N次合并操作将其全部连通时，总的操作量将达到 $N\ast N=N^2$ 次！
粗略估计，假设现在的计算机内存有 $10^9$ 个内存单元，CPU可以在每秒内执行 $10^9$ 次操作，那么计算机可以在1秒内访问一遍所有内存单元。而当我们有 $10^9$ 个对象，需要执行 $10^9$ 次合并操作时，消耗的时间为 $10^9$ 秒，约为30多年！很显然，在巨量的对象上运用这种算法，时间开销令人无法忍受。

后续将介绍动态连通性问题的两种新算法，更快，更强！。未完待续~
突然发现写完这一篇都没有写到树，挂羊头卖狗肉了属于是

参考：《Algorithms》Bob Sedgewick,Kevin Wayne. Princeton University.