并查集3
- 格式：doc
- 大小：171.00 KB
- 文档页数：8
课题1 并查集
研究时间：6.30~7.4
参考书目：
《算法艺术和信息学竞赛》——By 刘汝佳，黄亮
《数据结构（C语言版）》 ——By 严蔚敏，吴伟民
《算法与数据结构》 ——By 傅清祥，王晓东
《算法I—IV（C实现）》 ——By [美]Robert Sedgewick
【关键字】
并查集 联系问题 并查算法 等价关系和等价类 树和数组 启发式快速合并优化 压缩路径
【绪论】
在讲述并查集之前，我们来看一个很简单的问题：
一个简单题：联系问题
我们用实数对（p，q）表示p、q是相联系的。同样，实数对 (p,r) 代表 p 和 r 是相联系的。如果存在两个实数对（p,q）、（p,r），那么我们说， p,q,r 都是相联系的，即：具有传递性。我们的任务就是些程序来判断两个数是不是相联系的。
比如
有如下几个实数对 （ 1 ， 2 ）（ 2 ， 3 ）（ 3 ， 4 ）（ 4 ， 5 ）（ 1 ， 6 ）（ 2 ，
8 ）
我们需要问的是： 2 6 是不是相联系的。
——我们由题意可以很快得知：他们是相联系的。
(1 2 相联系， 1 6 相联系， 2 6 显然相联系！ )
分析
上面所说的问题实际上可以看成一个集合问题，将它数学化一点，就是 (p ， q) 就表示 p ，
q 在同样一个集合中，而最终我们要判断 x ， y 是不是在一个集合里面。很显然，题目不会告诉我们一个集合有多少个元素，分别是什么，他只会一次又一次地提示我们两个元素属于一个集合，而这个集合，就是我们所需要去构造的。然后，我们可以直接判断所询问的数
x ， y 在不在一个集合中。
拓展：
这类问题在现实中有着较为广泛应用及拓展：
1、 大型电网中，每次告诉我们两个点相联接，最后问 x ， y 是不是相联接
2、 亲戚问题： 每次告诉你某两个人之间存在亲戚关系，最后问： x ， y 是否是亲戚
从上面的例子中我们不难发现，在解决某些问题的时候，我们需要构造出一系列庞大的关系网络，而怎样才能很好的解决这些问题，我们现在要讨论的是一种算法——并查算法（ Union-Find Algorithms ） ，对应于它的抽象数据类型叫做——并查集
【 数学基础 】
首先，我们从数学的角度给出等价关系和等价类的定义：
定义： 如果集合 S 中的关系 R 是自反的，对称的，传递的，则称他为一个等价关系
——自反 x=x
——对称 若 x=y 则 y=x
——传递 若 x=y y=z 则 x=z
要求： x 、 y 、 z 必须要同一个子集中
定义： 如果 R 是集合 S 的等价关系。对于任何x∈S，由[x]R={y|y∈S and xRy}给出的集合[x]RS称为由x∈S生成的一个 R 的等价类。
定义： 若 R 是集合 S 上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以按 R 将 S 划分为若干不相交的子集 S1，S2，S3，S4 ……他们的并即为 S ，则这些子集 Si 变称为 S 的 R 等价类
划分等价类的问题的提法是：要求对 S 作出符合某些等价性条件的等价类的划分，已知集合 S 及一系列的形如“ x 等价于 y ”的具体条件，要求给出 S 的等价类的划分，符合所列等价性的条件。 < 我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合 S
划分成 n 个联系的子集，然后再判断 x ， y 是否在一个联系子集中 >
【 并查算法 】
我们仍然从绪论中的联系问题来入手。
开发一种高效算法来解决问题的第一步用一种简单的方法来解决问题。如果我们需要解决一些简单的特殊的具体情况，那么简单的程序就能够帮我们工作。但是若要做出一种高效算法，那简单的算法可以为我们提供一些一定范围内数据来验证我们的算法正确性。我们开发程序虽然要考虑效率，但是最基础而又最重要的是要确保解决问题正确性。
所以，我们首先想到的解决问题的方法是：储存所有输入的实数对，然后，写一个函数来，通过它来求出要求的实数对是否相联系。那么我们必须考虑以下几个问题：第一，如果数据很大，我们有没有那么多空间来储存这些实数对？第二，即使我们把所有的数据都储存了下来，我们也没有办法马上报出答案！ < 那储存所有数据就是费力不讨好的工作了 >
算法 I
program algorithm1
begin
readln(n);
for i:=1 to n do id[i]:=I;
while not eof do
begin
readln(p,q)
if id[p]=id[q] then
else begin
t:=id[q];
for i:=1 to n do
if id[i]=t then id[i]:=id[p]
end;
end;
end.
我们来讨论上面这种名为快速查找 (quick find) 的算法。
我们用数组的下标来表示集合名，并规定，一开始第 i 的集合包含集合 i 。如果 p 和 q 是相联系的，当且仅当 p 号元素和 q 号元素他们的数据值（即表示他们所在的集合）相等。为了表现出对 p 和 q 进行并操作，我们扫描整个数组，改变所有数据值和 p 相同的，变为 q 。当然这种选择是任意的，我们也可以把数据值和 q 相同的，变为 p 。这个操作如果要进行查找，那么就是直接查找就可以了。
性质： 快速查找的算法至少执行 M*N 次命令来解决一个有 n 个事物和 m 次和并操作的联系问题
小结： 现代计算机每秒执行一亿到十亿次命令，所以当 M 和 N 很小的时候，我们不会察觉到算法的优劣。但是我们同样可以找到几百万个事物，几十亿次合并的命令，所以这样的算法就很难承受了。
算法 II
我们接下来考虑的是另一种叫做快速合并 (quick-union) 算法。我们设定每一个事物指向同一个集合里面的另一个事物，并且是一个无环的结构。决定两个事物是不是在同一个集合，我们移动每一个的指针一直指向他们的根，两个事物在同一个集合里面，当且仅当我们的根相等。如果他们不在同一个集合里面，我们将停在不同的事物上面。对于并操作，我们只需要将一个的父亲连接到另一个的根的下面。这就是为什么这种算法成为快速合并
(quick-union) 算法的原因！这种算法明显优于第一种算法，为什么？因为它没有反复地对数组进行扫描，确切地说，它不需要反复扫描。
性质： 对于 M>N ，快速合并算法将执行超过 M*N/2 次命令来解决由 M 对 N 个事物的联系问题
program algorithm2
begin
i:=p;
while i<>id[i] do i:=id[i];
j:=q;
while j<>id[j] do j:=id[j];
if i=j then
else id[i]=j
end;
{ 上面的两个循环语句就是为了找到 i 和 j 所在的集合的根，然后在合并 }
小结： 这种方法有一个很大的缺陷，我们来讨论一下：如果输入数据是 1~2 ， 2~3 ， 3~4
那么在 n-1 次输入后，我们就有了 n 个事物在集合中，那么它的图像（一棵树）就会将近成为一条直线。那么，在执行查找操作的时候，对于查找 n ，我们需要移动 n-1 次指针，因此，平均的移动指针数量是：
（ 0+1+2+ …… +(n-1) ） /n=(n-1)/2 。
如果我们所有的情况都是这样的，很显然， m 对 N 个事物的联系，将会大于 M*N/2 次操作。
优化I
上面这种算法虽然较为优秀，但是我们也看到了其在最坏情况下的复杂度，显然这种算法我们依然难以接受。不过幸运地，我们有一种修正的方法来解决这个问题，即第一种对于并查集的优化，算法的思想在于把深度小的树合并到深度大的树中间去，以至于平衡整个结果的深度，这样的话，我们将避免出现上述的 bad case 。当然，我们需要的是多一些的代码，和另外一个数组，用来记录深度。这样将把程序的效率大大地提高。我们称为启发式快速合并（ weighted quick-union ）算法。
这种启发式快速合并的算法，我们发现即使在平常情况下都比，集合树都比不优化的情况下，深度小。 我们用图形的方式为大家展示一下他们的区别。1 2
3 4
5 6 7 8 9 0
3 4 1 2 3
4 5
6 7 8 9 0
1 2
3 5
4 6 7 8 9 0 4 9
1 2
3 5
4 6 7 8 9
0 0 8
1
2
3 5
4 6 7 8 9
0
1
2
3 5 4 6 7 8 9
0 5 6
1
2
3 5 4 6 7 8 9
0 2 9 不变
5 9
1
2
3 5 4 6 7 8 9
0 7 3
1
2
3 5 4 6 7 8 9 0
6 1 1
2
3 5 4 6 7 8 9 0 0 2不变 4 8 这是一个普通方法，即快速合并的基础方法的示意图。我并没有把书的枝条画出来
大家可以看到最后的结果，已经到了5层的树了
2 3
那么，这样的话我们发现，如果有2n个节点，我们只需要将指针移动n次就可以找到我们需要的事物，这就大大提高了效率。
性质：启发式快速合并算法最多移动2logN次指针就可以决定两个事物是否想联系。
我们可以证明，在一个有k个元素的集合，我们将保证移动不超过logk次就可以找到目标。
证明：我们合并一个有i个结点的集合和一个有j个结点的集合，我们设i<=j，我们在一个小的集合中增加一个被跟随的指针，但是他们现在在一个数量为i+j的集合中。由于)ji(log)ii(loglogi1，所以我们可以保证性质。
< Prove: When we combine a set of i nodes with a set of j nodes with i<=j, we 1 2
