动态连通性问题简述

动态连通性问题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_i ai​ 与 a j a_j aj​ 连通 ( i , j = 1 , 2 , 3 , … , n i,j=1,2,3,…,n i,j=1,2,3,…,n)。
   示意图：
   

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

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

抽象模型

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

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

1. 自反性：每一个对象都与它本身连通，即 i i i 与 i i i 连通
2. 对称性：如果 i i i 与 j j j 连通，那么 j j j 与 i i i 也连通
3. 传递性：如果 i i i 与 j j j 连通， j j j 与 k k k 连通，那么 i i i 与 k k 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是否连通的函数
};

算法设计与实现

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

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

index	0	1	2	3	4	5	6	7	8	9
value	1	1	1	8	8	1	1	1	8	8

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

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

1.DynamicConnectivity(int N)：

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

index	0	1	2	3	4	5	6	7	8	9
value	0	1	2	3	4	5	6	7	8	9

代码实现：

DynamicConnectivity::DynamicConnectivity(int N)
{
	id = new int[N];
	for (int i = 0; i < N; i++)
		id[i] = i;
}

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)

index	0	1	2	3	4	5	6	7	8	9
value	1	1	2	3	4	5	6	7	8	9

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

Union(2,1)

index	0	1	2	3	4	5	6	7	8	9
value	1	1	1	3	4	5	6	7	8	9

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

Union(5,2)

index	0	1	2	3	4	5	6	7	8	9
value	1	1	1	3	4	1	6	7	8	9

“将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;
}

经典错误：

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

3.isConnected(int p, int q)

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

代码实现：

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

算法分析

时间复杂度

算法	初始化函数 DynamicConnectivity(int N)	合并函数 Union(int p,int q)	查找函数 isConnected(int p,int q)
快速查找 Quick-find	O(N)	O(N)	O(1)

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

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

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

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