数据结构与算法分析读书笔记系列08-不想交集ADT

在这一部分，我们描述解决等价问题的一种有效数据结构。

若对于每一对元素(a, b),a,b∈ S,aRb或者为true或者为false，则称在集合S上定义关系(relation)R。如果aRb是true，那么我们说a与b有关系。

等价关系(equivalence relation)是满足下列三个性质的关系R:

1. (自反性)对于所有的a ∈ S, aRa。
2. (对称性)aRb当且仅当bRa。
3. (传递性)若aRb且bRc则aRc。

例子：

关系"≤"不是等价关系。虽然它是自反的，可传递的，但它不是对称的。

电气连通性(electrical connectivity)是一个等价关系，其中所有的连接都是通过金属导线完成的。该关系显然是自反的，因为任何元件都是自身相连的。如果a电气连接b，那么b必然也电气连接到a。最后，如果a连接b，而b又连接c，那么a连接到c。因此，电气连接是一个等价关系。

如果两个城市位于同一个国家，那么定义它们是有关系的。容易验证这是一个等价关系。

给定一个等价关系"∼"，一个自然的问题对任意的a和b，确定是否a ∼ b。如果将等价关系存储为一个二维布尔数组，那么当然这个工作可以以常数时间完成。问题在于，这种关系的定义通常不明显，而是相当隐秘。

一个元素a ∈ S的等价类(equivalence class)是S的一个子集，它包含所有与a有关系的元素。注意，等价类形成对S的划分：S的每一个成员恰好出现在一个等价类中。为确定a ∈ b，我们只需要验证a和b是否都在同一个等价类中。这给我们提供了解决等价问题的方法。

输入数据最初是N个集合的类(collection)，每个集合含有一个元素。初始的描述是所有的关系均为false(自反的关系除外)。每个集合都有一个不同的元素，从而S_i ∩ S_j = ∅ ；这使得这些集合不相交(disjoint)。

此时，有两种运算允许进行。第一种运算是Find，它返回包含给定元素的集合(即等价类)的名字。第二种运算是添加关系。如果我们想要添加关系 a ∼ b ，那么我们首先要看是否a和b已经有关系。这可以通过对a和b执行Find并检验它们是否在同一个等价类中来完成。如果它们不在同一类中，那么我们使用求并运算Union，这种运算把含有a和b的两个等价类合并成一个新的等价类。从集合的观点来看，∪ 的结果是建立一个新集合S_k = S_i ∪ S_j ，去掉原来两个集合而保持所有集合的不相交性。由于这个原因，常常把这项工作的算法叫做不相交集的Union/Find算法。

解决动态等价问题的方案有两种。一种方案保证指令Find能够以常数最坏情形运行时间执行，而另一种方案则保证指令Union能够以常数最坏时间执行。

为是Find运算快，可以在一个数组中保存每个元素的等价类的名字。一种想法是将所有在同一个等价类中的元素放到一个链表中。这样在更新的时候会节省时间，因为我们不必搜索整个数组。

后面的部分，将介绍Union/Find问题的一种解法，其中Union运算容易但是Find运算要难一些。即使如此，任意顺序的最多M次Find和直到N-1次Union的运算时间只比O(M + N)多一点。

记住，我们的问题不要求Find操作返回任何特定的名字，而只是要求当且仅当两个元素属于相同的集合时，作用在这两个元素上的Find返回相同的名字。一种想法是可以使用树来表示每一个集合，因为树上的每个元素都有相同的根。这样，该根就可以用来命名所在的集合。我们将用树表示每一个集合。（记住，树的集合叫做森林。）开始时每个集合含有一个元素。

图8-6到图8-9的程序表示基本算法的实现，假设差错检验已经执行。在我们的例程中，这些Union是在这些树的根上进行的。有时候运算是通过任意两个元素进行，并使得Union执行两次Find以确定这些根。

上面的Union的执行是相当任意的，它通过使第二棵树成为第一棵树的子树而完成合并。对其进行简单改进是借助任意的方法打破现有关系，使得总让较小的树成为较大的树的子树；我们把这种方法叫做按大小求并(union-by-size)。为了实现这种方法，我们需要记住每一棵树的大小。由于我们实际上只使用一个数组，因此可以让每个根的数组元素包含它的树的大小的负值。这样一来，初始时树的数组表示就都是-1。

另一种实现方法为按高度求并(union-by-height)，它同样保证所有的树的深度最多是O(logN)。我们跟踪每棵树的高度而不是大小并执行那些Union使得浅的树成为深的树的子树。这是一种平缓的算法，因为只有当两棵相等深度的树求并时树的高度才增加(此时树的高度增1)。这样，按高度求并是按大小求并的简单修改。

下列各图显示一棵树以及它对于按大小求并和按高度求并的非显示表示。图8-13中的程序实现的是按高度求并的代码。

迄今所描述的Union/Find算法对于大多数的情形都是完全可接受的，它非常简单的，而且对于连续M个指令(在所有的模型下)平均是线性的。不过，O(MlogN)的最坏情形还是可能相当容易并自然地发生的。而且应该清楚，对于Union算法恐怕没有更多改进的可能。这是基于这样的观察：执行Union操作的任何算法都将产生相同的最坏情形的树，因为它必然会随意打破树间的均衡。因此，无须对整个数据结构重新加工而使算法加速的惟一方法是对Find操作做些更聪明的工作。

这种聪明的操作叫做路径压缩(path compression)。路径压缩在一次Find操作期间执行而与用来执行Union的方法无关。该操作为Find(X)，此时路径压缩的效果是，从X到根的路径上的每个节点都使它的父节点变成根。

正如图8-15中的程序所指出的，路径压缩对基本的Find操作改变不大。对Find例程来说，惟一的变化是使得S[X]等于由Find返回的值；这样，在集合的根被递归地找到以后，X就直接指向它。对通向根的路径上的每个节点这将递归地出现，因此实现了路径压缩。

当任意执行一些Union操作的时候，路径压缩是一个好的想法，因为存在许多深层节点并通过路径压缩将它们移近根节点。

路径压缩与按大小求并完全兼容，这就使得两个例程可以同时实现。

路径压缩不完全与按高度求并兼容，因为路径压缩可以改变树的高度。此时，对于每棵树所存储的高度是估计的高度(有时称为秩——rank)，实际上按秩求并理论上和按大小求并效率是一样的。

太复杂了，没看。

我们有一个计算机网络和一个双向链表；每一个连接可将文件从一台计算机传送到另一台计算机。那么能否将一个文件从网络上的任意一台计算机发送到任意的另一台计算机上去呢？一个附加的限制是要求该问题必须联机(on-line)解决。因此，这个连接表要一次一个地给出，而算法则必须能够在任一时刻给出答案。

解决这个问题的一个算法可以在开始时把每一台计算机放到它自己的集合中。我们要求两台计算机可以传输文件当且仅当它们在同一个集合中。可以看出，传输文件的能力形成一个等价关系。

介绍了保持不相交集合的非常简单的数据结构。当Union操作执行时，就正确性而言，哪个集合保留它的名字是无关紧要的。这里，有必要注意，当某一步尚未完全指定的时候，考虑选择方案可能是非常重要的，Union是灵活的；借助这一点，我们能够得到一个有效的多的算法。

路径压缩是自调整(self-adjustment)的最早形式之一，在别的一些地方(伸展树，斜堆)见到过。它的使用非常有趣，特别从理论的观点来看，因为它是算法简单但是最坏情形分析复杂的例子之一。