1.5 案例研究：union-find算法

为了说明我们设计和分析算法的基本方法，我们现在来学习一个具体的例子。我们的目的是强调以下几点：

❏优秀的算法因为能够解决实际问题而变得更为重要；

❏高效算法的代码也可以很简单；

❏理解某个实现的性能特点是一项有趣而令人满足的挑战；

❏在解决同一个问题的多种算法之间进行选择时，科学方法是一种重要的工具；

❏迭代式改进能够让算法的效率越来越高。

我们会在本书中不断巩固这些主题思想。本节中的例子是一个原型，它将会为我们用相同的方法解决许多其他问题打下坚实的基础。

我们将要讨论的问题并非无足轻重，它是一个非常基础的计算性问题，而我们开发的解决方案将会用于多种实际应用之中，从物理化学中的渗流到通信网络中的连通性等。我们首先会给出一个简单的方案，然后对它的性能进行研究并由此得出应该如何继续改进我们的算法。

1.5.1 动态连通性

首先我们详细地说明一下问题：问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数p q可以被理解为“p和q是相连的”。我们假设“相连”是一种等价关系，这也就意味着它具有：

❏自反性：p和p是相连的；

❏对称性：如果p和q是相连的，那么q和p也是相连的；

❏传递性：如果p和q是相连的且q和r是相连的，那么p和r也是相连的。

等价关系能够将对象分为多个等价类。在这里，当且仅当两个对象相连时它们才属于同一个等价类。我们的目标是编写一个程序来过滤掉序列中所有无意义的整数对（两个整数均来自于同一个等价类中）。换句话说，当程序从输入中读取了整数对p q时，如果已知的所有整数对都不能说明p和q是相连的，那么则将这一对整数写入到输出中。如果已知的数据可以说明p和q是相连的，那么程序应该忽略p q这对整数并继续处理输入中的下一对整数。图1.5.1用一个例子说明了这个过程。为了达到所期望的效果，我们需要设计一个数据结构来保存程序已知的所有整数对的足够多的信息，并用它们来判断一对新对象是否是相连的。我们将这个问题通俗地叫做动态连通性问题。这个问题可能有以下应用。

1.5.1.1 网络

输入中的整数表示的可能是一个大型计算机网络中的计算机，而整数对则表示网络中的连接。这个程序能够判定我们是否需要在p和q之间架设一条新的连接才能进行通信，或是我们可以通过已有的连接在两者之间建立通信线路；或者这些整数表示的可能是电子电路中的触点，而整数对表示的是连接触点之间的电路；或者这些整数表示的可能是社交网络中的人，而整数对表示的是朋友关系。在此类应用中，我们可能需要处理数百万的对象和数十亿的连接。

1.5.1.2 变量名等价性

某些编程环境允许声明两个等价的变量名（指向同一个对象的多个引用）。在一系列这样的声明之后，系统需要能够判别两个给定的变量名是否等价。这种较早出现的应用（如FORTRAN语言）推动了我们即将讨论的算法的发展。

1.5.1.3 数学集合

在更高的抽象层次上，可以将输入的所有整数看做属于不同的数学集合。在处理一个整数对p q时，我们是在判断它们是否属于相同的集合。如果不是，我们会将p所属的集合和q所属的集合归并到同一个集合。

为了进一步限定话题，我们会在本节以下内容中使用网络方面的术语，将对象称为触点，将整数对称为连接，将等价类称为连通分量或是简称分量。简单起见，假设我们有用0到N-1的整数所表示的N个触点。这样做并不会降低算法的通用性，因为我们在第3章中将会学习一组高效的算法，将整数标识符和任意名称关联起来。

图1.5.2是一个较大的例子，意在说明连通性问题的难度。你很快就可以找到图左侧中部一个只含有一个触点的分量，以及左下方一个含有5个触点的分量，但让你验证其他所有触点是否都是相互连通的可能就有些困难了。对于程序来说，这个任务更加困难，因为它所处理的只有触点的名字和连接而并不知道触点在图像中的几何位置。我们如何才能快速知道这种网络中任意给定的两个触点是否相连呢？

我们在设计算法时面对的第一个任务就是精确地定义问题。我们希望算法解决的问题越大，它完成任务所需的时间和空间可能就越多。我们不可能预先知道这其间的量化关系，而且我们通常只会在发现解决问题很困难，或是代价巨大，或是在幸运地发现算法所提供的信息比原问题所需要的更加有用时修改问题。例如，连通性问题只要求我们的程序能够判别给定的整数对p q是否相连，但并没有要求给出两者之间的通路上的所有连接。这样的要求会使问题更加困难，并得到另一组不同的算法，我们会在4.1节中学习它们。

为了说明问题，我们设计了一份API来封装所需的基本操作：初始化、连接两个触点、判断包含某个触点的分量、判断两个触点是否存在于同一个分量之中以及返回所有分量的数量。详细的API如表1.5.1所示。

如果两个触点在不同的分量中，union()操作会将两个分量归并。find()操作会返回给定触点所在的连通分量的标识符。connected()操作能够判断两个触点是否存在于同一个分量之中。count()方法会返回所有连通分量的数量。一开始我们有N个分量，将两个分量归并的每次union()操作都会使分量总数减一。

我们马上就将看到，为解决动态连通性问题设计算法的任务转化为了实现这份API。所有的实现都应该：

❏定义一种数据结构表示已知的连接；

❏基于此数据结构实现高效的union()、find()、connected()和count()方法。

众所周知，数据结构的性质将直接影响到算法的效率，因此数据结构和算法的设计是紧密相关的。API已经说明触点和分量都会用int值表示，所以我们可以用一个以触点为索引的数组id[]作为基本数据结构来表示所有分量。我们将使用分量中的某个触点的名称作为分量的标识符，因此你可以认为每个分量都是由它的触点之一所表示的。一开始，我们有N个分量，每个触点都构成了一个只含有它自己的分量，因此我们将id[i]的值初始化为i，其中i在0到N-1之间。对于每个触点i，我们将find()方法用来判定它所在的分量所需的信息保存在id[i]之中。connected()方法的实现只用一条语句find(p) == find(q)，它返回一个布尔值，我们在所有方法的实现中都会用到connected()方法。

总之，我们的起点就是算法1.5。我们维护了两个实例变量，一个是连通分量的个数，一个是数组id[]。find()和union()的实现是本节剩余内容将要讨论的主题。

算法1.5 union-find的实现

public class UF
{
    private int[] id;      // 分量id（以触点作为索引）
    private int count;    // 分量数量
    public UF(int N)
    {  // 初始化分量id数组
        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)
    public void union(int p, int q)
    // 请见1.5.2.1节用例（quick-find）、1.5.2.3节用例（quick-union）和算法1.5（加权quick-union）
    public static void main(String[] args)
    {  // 解决由StdIn得到的动态连通性问题
        int N = StdIn.readInt();                // 读取触点数量
        UF uf = new UF(N);                      // 初始化N个分量
        while (! StdIn.isEmpty())
        {
          int p = StdIn.readInt();
          int q = StdIn.readInt();            // 读取整数对
          if (uf.connected(p, q)) continue;  // 如果已经连通则忽略
          uf.union(p, q);                      // 归并分量
          StdOut.println(p + " " + q);       // 打印连接
        }
        StdOut.println(uf.count() + "components");
    }
}

这份代码是我们对UF的实现。它维护了一个整型数组id[]，使得find()对于处在同一个连通分量中的触点均返回相同的整数值。union()方法必须保证这一点。

为了测试API的可用性并方便开发，我们在main()方法中包含了一个用例用于解决动态连通性问题。它会从输入中读取N值以及一系列整数对，并对每一对整数调用connected()方法：如果某一对整数中的两个触点已经连通，程序会继续处理下一对数据；如果不连通，程序会调用union()方法并打印这对整数。在讨论实现之前，我们也准备了一些测试数据（如右侧的代码框所示）：文件tinyUF.txt含有10个触点和11条连接，图1.5.1使用的就是它；文件mediumUF. txt含有625个触点和900条连接，如图1.5.2所示；例子文件largeUF.txt含有100万个触点和200万条连接。我们的目标是在可以接受的时间范围内处理和largeUF.txt规模类似的输入。

为了分析算法，我们将重点放在不同算法访问任意数组元素的总次数上。我们这样做相当于隐式地猜测各种算法在一台特定的计算机上的运行时间在这个量乘以某个常数的范围之内。这个猜想基于代码，用实验验证它并不困难。我们将会看到，这个猜想是算法比较的一个很好的开始。

union-find的成本模型。在研究实现union-find的API的各种算法时，我们统计的是数组的访问次数（访问任意数组元素的次数，无论读写）。

1.5.2 实现

我们将讨论三种不同的实现，它们均根据以触点为索引的id[]数组来确定两个触点是否存在于相同的连通分量中。

1.5.2.1 quick-find算法

一种方法是保证当且仅当id[p]等于id[q]时p和q是连通的。换句话说，在同一个连通分量中的所有触点在id[]中的值必须全部相同。这意味着connected(p, q)只需要判断id[p] ==id[q]，当且仅当p和q在同一连通分量中该语句才会返回true。为了调用union(p, q）确保这一点，我们首先要检查它们是否已经存在于同一个连通分量之中。如果是我们就不需要采取任何行动，否则我们面对的情况就是p所在的连通分量中的所有触点的id[]值均为同一个值，而q所在的连通分量中的所有触点的id[]值均为另一个值。要将两个分量合二为一，我们必须将两个集合中所有触点所对应的id[]元素变为同一个值，如表1.5.2所示。为此，我们需要遍历整个数组，将所有和id[p]相等的元素的值变为id[q]的值。我们也可以将所有和id[q]相等的元素的值变为id[p]的值——两者皆可。根据上述文字得到的find()和union()的代码简单明了，如下面的代码框所示。图1.5.3显示的是我们的开发用例在处理测试数据tinyUF.txt时的完整轨迹。

1.5.2.2 quick-find算法的分析

find()操作的速度显然是很快的，因为它只需要访问id[]数组一次。但quick-find算法一般无法处理大型问题，因为对于每一对输入union()都需要扫描整个id[]数组。

假设我们使用quick-find算法来解决动态连通性问题并且最后只得到了一个连通分量，那么这至少需要调用N-1次union()，即至少（N+3）（N-1）～N2次数组访问——我们马上可以猜想动态连通性的quick-find算法是平方级别的。将这种分析推广我们可以得到，quick-find算法的运行时间对于最终只能得到少数连通分量的一般应用是平方级别的。在计算机上用倍率测试可以很容易验证这个猜想（指导性的例子请见练习1.5.23）。现代计算机每秒钟能够执行数亿甚至数十亿条指令，因此如果N较小的话这个成本并不是很明显。但是在现代应用中我们也很可能需要处理几百万甚至数十亿的触点和连接，例如我们的测试文件largeUF.txt。如果你还不相信并且觉得自己的计算机足够快，请使用quick-find算法找出largeUF.txt中所有整数对所表示的连通分量的数量。结论无可争议，使用quick-find算法解决这种问题是不可行的，我们需要寻找更好的算法。

1.5.2.3 quick-union算法

我们要讨论的下一个算法的重点是提高union()方法的速度，它和quick-find算法是互补的。它也基于相同的数据结构——以触点作为索引的id[]数组，但我们赋予这些值的意义不同，我们需要用它们来定义更加复杂的结构。确切地说，每个触点所对应的id[]元素都是同一个分量中的另一个触点的名称（也可能是它自己）——我们将这种联系称为链接。在实现find()方法时，我们从给定的触点开始，由它的链接得到另一个触点，再由这个触点的链接到达第三个触点，如此继续跟随着链接直到到达一个根触点，即链接指向自己的触点（你将会看到，这样一个触点必然存在）。当且仅当分别由两个触点开始的这个过程到达了同一个根触点时它们存在于同一个连通分量之中。为了保证这个过程的有效性，我们需要union(p, q)来保证这一点。它的实现很简单：我们由p和q的链接分别找到它们的根触点，然后只需将一个根触点链接到另一个即可将一个分量重命名为另一个分量，因此这个算法叫做quick-union。和刚才一样，无论是重命名含有p的分量还是重命名含有q的分量都可以，右侧的这段实现重命名了p所在的分量。图1.5.5显示了quick-union算法在处理tinyUF.txt时的轨迹。图1.5.4能够很好地说明图1.5.5（见1.5.2.4节）中的轨迹，我们接下来要讨论的就是它。

1.5.2.4 森林的表示

quick-union算法的代码很简洁，但有些难以理解。用节点（带标签的圆圈）表示触点，用从一个节点到另一个节点的箭头表示链接，由此得到数据结构的图像表示使我们理解算法的操作变得相对容易。我们的得到的结构是树——从技术上来说，id[]数组用父链接的形式表示了一片森林。为了简化图表，我们常常会省略链接的箭头（因为它们的指向全部朝上）和树的根节点中指向自己的链接。tinyUF.txt的id[]数组所对应的森林如图1.5.5所示。无论我们从任何触点所对应的节点开始跟随链接，最终都将达到含有该节点的树的根节点。可以用归纳法证明这个性质的正确性：在数组被初始化之后，每个节点的链接都指向它自己；如果在某次union()操作之前这条性质成立，那么操作之后它必然也成立。因此，quick-union中的find()方法能够返回根节点所对应的触点的名称（这样connected()才能够判定两个触点是否在同一棵树中）。这种表示方法对于这个问题很实用，因为当且仅当两个触点存在于相同的分量之中时它们对应的节点才会在同一棵树中。另外，构造树并不困难：quick-union中union()的实现只用了一条语句就将一个根节点变为另一个根节点的父节点，从而归并了两棵树。

1.5.2.5 quick-union算法的分析

quick-union算法看起来比quick-find算法更快，因为它不需要为每对输入遍历整个数组。但它能够快多少呢？分析quick-union算法的成本比分析quick-find算法的成本更困难，因为这依赖于输入的特点。在最好的情况下，find()只需要访问数组一次就能够得到一个触点所在的分量的标识符；而在最坏情况下，这需要2N+1次数组访问，如图1.5.6中的0触点（这个估计是较为保守的，因为while循环中经过编译的代码对id[p]的第二次引用一般都不会访问数组）。由此我们不难构造一个最佳情况的输入使得解决动态连通性问题的用例的运行时间是线性级别的；另一方面，我们也可以构造一个最坏情况的输入，此时它的运行时间是平方级别的（请见图1.5.6和下面的命题G）。幸好我们不需要面对分析quick-union算法的问题，我们也不会仔细对比quick-union算法和quick-find算法的性能，因为我们下面将会学习一种比两者的效率都高得多的算法。目前，我们可以将quick-union算法看做是quick-find算法的一种改良，因为它解决了quick-find算法中最主要的问题（union()操作总是线性级别的）。对于一般的输入数据这个变化显然是一次改进，但quick-union算法仍然存在问题，我们不能保证在所有情况下它都能比quick-find算法快得多（对于某些输入，quick-union算法并不比quick-find算法快）。

同样，假设我们使用quick-union算法解决了动态连通性问题并最终只得到了一个分量，由命题G我们马上可以知道算法的运行时间在最坏情况下是平方级别的。假设输入的整数对是有序的0-1、0-2、0-3等，N-1对之后我们的N个触点将全部处于相同的集合之中且由quick-union算法得到的树的高度为N-1，其中0链接到1,1链接到2,2链接到3，如此下去（请见图1.5.6）。由命题G可知，对于整数对0-i, union()操作访问数组的次数为2i+1（触点0的深度为i-1，触点i的深度为0）。因此，处理N对整数所需的所有find()操作访问数组的总次数为3+5+7+…+（2N-1）～N2。

1.5.2.6 加权quick-union算法

幸好，我们只需简单地修改quick-union算法就能保证像这样的糟糕情况不再出现。与其在union()中随意将一棵树连接到另一棵树，我们现在会记录每一棵树的大小并总是将较小的树连接到较大的树上。这项改动需要添加一个数组和一些代码来记录树中的节点数，如算法1.5所示，但它能够大大改进算法的效率。我们将它称为加权quick-union算法（如图1.5.7所示）。该算法在处理tinyUF.txt时构造的森林如图1.5.8中左侧的图所示。即使对于这个较小的例子，该算法构造的树的高度也远远小于未加权的版本所构造的树的高度。

1.5.2.7 加权quick-union算法的分析

图1.5.8显示了加权quick-union算法的最坏情况。其中将要被归并的树的大小总是相等的（且总是2的幂）。这些树的结构看起来很复杂，但它们均含有2n个节点，因此高度都正好是n。另外，当我们归并两个含有2n个节点的树时，我们得到的树含有2n+1个节点，由此将树的高度增加到了n+1。由此推广我们可以证明加权quick-union算法能够保证对数级别的性能。加权quick-union算法的实现如算法1.5所示。

% java WeightedQuickUnionUF ＜ mediumUF.txt
528503
548523
...
3 components
% java WeightedQuickUnionUF ＜ largeUF.txt
786321134521
69683498245
...
6 components

算法1.5（续）union-find算法的实现（加权quick-union算法）

public class WeightedQuickUnionUF
{
    private int[] id;      // 父链接数组（由触点索引）
    private int[] sz;      //（由触点索引的）各个根节点所对应的分量的大小
    private int count;    // 连通分量的数量
    public WeightedQuickUnionUF(int N)
    {
      count = N;
      id = new int[N];
      for (int i = 0; i ＜ N; i++) id[i] = i;
      sz = new int[N];
      for (int i = 0; i ＜ N; i++) sz[i] = 1;
    }
    public int count()
    {  return count;  }
    public boolean connected(int p, int q)
    {  return find(p) == find(q);  }
    public int find(int p)
    {  // 跟随链接找到根节点
      while (p ! = id[p]) p = id[p];
      return p;
    }
    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--;
    }
}

根据正文所述的森林表示方法这段代码很容易理解。我们加入了一个由触点索引的实例变量数组sz[]，这样union()就可以将小树的根节点连接到大树的根节点。这使得算法能够处理规模较大的问题。

对于动态连通性问题，命题H和它的推论的实际意义在于加权quick-union算法是三种算法中唯一可以用于解决大型实际问题的算法。加权quick-union算法处理N个触点和M条连接时最多访问数组cMlgN次，其中c为常数。这个结果和quick-find算法（以及某些情况下的quick-union算法）需要访问数组至少MN次形成了鲜明的对比。因此，有了加权quick-union算法我们就能保证能够在合理的时间范围内解决实际中的大规模动态连通性问题。只需要多写几行代码，我们所得到的程序在处理实际应用中的大型动态连通性问题时就会比简单的算法快数百万倍。

图1.5.9显示的是一个含有100个触点的例子。从图中我们可以很明显地看到，加权quick-union算法中远离根节点的节点相对较少。事实上，只含有一个节点的树被归并到更大的树中的情况很常见，这样该节点到根节点的距离也只有一条链接而已。针对大规模问题的经验性研究告诉我们，加权quick-union算法在解决实际问题时一般都能在常数时间内完成每个操作（如表1.5.3所示）。我们可能很难找到比它效率更高的算法了。

1.5.2.8 最优算法

我们可以找到一种能够保证在常数时间内完成各种操作的算法吗？这个问题非常困难并且困扰了研究者们许多年。在寻找答案的过程中，大家研究了quick-union算法和加权quick-union算法的各种变体。例如，下面这种路径压缩方法很容易实现。理想情况下，我们希望每个节点都直接链接到它的根节点上，但我们又不想像quick-find算法那样通过修改大量链接做到这一点。我们接近这种理想状态的方式很简单，就是在检查节点的同时将它们直接链接到根节点。这种方法乍一看很激进，但它的实现非常容易，而且这些树并没有阻止我们进行这种修改的特殊结构：如果这么做能够改进算法的效率，我们就应该实现它。要实现路径压缩，只需要为find()添加一个循环，将在路径上遇到的所有节点都直接链接到根节点。我们所得到的结果是几乎完全扁平化的树，它和quick-find算法理想情况下所得到的树非常接近。这种方法即简单又有效，但在实际情况下已经不太可能对加权quick-union算法继续进行任何改进了（请见练习1.5.24）。对该情况的理论研究结果非常复杂也值得我们注意：路径压缩的加权quick-union算法是最优的算法，但并非所有操作都能在常数时间内完成。也就是说，使用路径压缩的加权quick-union算法的每个操作在在最坏情况下（即均摊后）都不是常数级别的，而且不存在其他算法能够保证union-find算法的所有操作在均摊后都是常数级别的（在非常一般的cell probe模型之下）。使用路径压缩的加权quick-union算法已经是我们对于这个问题能够给出的最优解了。

1.5.2.9 均摊成本的图像

与对其他任何数据结构实现的讨论一样，我们应该按照1.4节中的讨论在实验中用典型的用例验证我们对算法性能的猜想。图1.5.10详细显示了我们的动态连通性问题的开发用例在使用各种算法处理一份含有625个触点的样例数据（mediumUF.txt）时的性能。绘制这种图像很简单（请见练习1.5.16）：在处理第i个连接时，用一个变量cost记录其间访问数组（id[]或sz[]）的次数，并用一个变量total记录到目前为止数组访问的总次数。我们在(i, cost)处画一个灰点，在(i, total/i)处画一个红点，红点表示的是每个操作的平均成本，即均摊成本。图像能够帮助我们更好地理解算法的行为。对于quick-find算法，每次union()操作都至少访问数组625次（每归并一个分量还要加1，最多再加625），每次connected()操作都访问数组2次。一开始，大多数连接都会产生一个union()调用，因此累计平均值徘徊在625左右；后来，大多数连接产生的connected()调用会跳过union()，因此累计平均值开始下降，但仍保持了相对较高的水平（能够产生大量connected()调用并跳过union()的输入性能要好得多，例子请见练习1.5.23）。对于quick-union算法，所有的操作在初始阶段访问数组的次数都不多；到了后期，树的高度成为一个重要因素，均摊成本的增长很明显。对于加权quick-union算法，树的高度一直很小，没有任何昂贵的操作，均摊成本也很低。这些实验验证了我们的结论，显然非常有必要实现加权quick-union算法，在解决实际问题时已经没有多少进一步改进的空间了。

1.5.3 展望

直观感觉上，我们学习的每种UF的实现都改进了上一个版本的实现，但这个过程并不突兀，因为我们可以总结学者们对这些算法多年的研究。我们很明确地说明了问题，解决方法的实现也很简单，因此可以用经验性的数据评估各个算法的优劣。另外，还可以通过这些研究验证将算法的性能量化的数学结论。只要可能，我们在本书中研究各种基础问题时都会遵循类似于本节中讨论union-find问题时的基本步骤，在这里我们要再次强调它们。

❏完整而详细地定义问题，找出解决问题所必需的基本抽象操作并定义一份API。

❏简洁地实现一种初级算法，给出一个精心组织的开发用例并使用实际数据作为输入。

❏当实现所能解决的问题的最大规模达不到期望时决定改进还是放弃。

❏逐步改进实现，通过经验性分析或（和）数学分析验证改进后的效果。

❏用更高层次的抽象表示数据结构或算法来设计更高级的改进版本。

❏如果可能尽量为最坏情况下的性能提供保证，但在处理普通数据时也要有良好的性能。

❏在适当的时候将更细致的深入研究留给有经验的研究者并继续解决下一个问题。

我们从union-find问题中可以看到，算法设计在解决实际问题时能够为程序的性能带来惊人的提高，这种潜力使它成为热门研究领域。还有什么其他类型的设计行为可能将成本降为原来的数百万甚至数十亿分之一呢？

设计高效的算法是一种很有成就感的智力活动，同时也能够产生直接的实际效益。正如动态连通性问题所示，为解决一个简单的问题我们学习了许多算法，它们不但有用有趣，也精巧而引人入胜。我们还将遇到许多新颖独特的算法，它们都是人们在数十年以来为解决许多实际问题而发明的。随着计算机算法在科学和商业领域的应用范围越来越广，能够使用高效的算法来解决老问题并为新问题开发有效的解决方案也越来越重要了。

答疑

问 我希望为API添加一个delete()方法来允许用例删除连接。能够给我一些建议吗？

答 目前还没有人能够发明既能处理删除操作而又和本节中所介绍的算法同样简单而高效的算法。这个主题在本书中会反复出现。在我们讨论的一些数据结构中删除比添加要困难得多。

问 cell-probe模型是什么？

答 它是一种计算模型，其中我们只会记录对随机内存的访问，内存大小足以保存所有输入且假设其他操作均没有成本。

练习

1.5.1 使用quick-find算法处理序列9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2。对于输入的每一对整数，给出id[]数组的内容和访问数组的次数。

1.5.2 使用quick-union算法（请见1.5.2.3节代码框）完成练习1.5.1。另外，在处理完输入的每对整数之后画出id[]数组表示的森林。

1.5.3 使用加权quick-union算法（请见算法1.5）完成练习1.5.1。

1.5.4 在正文的加权quick-union算法示例中，对于输入的每一对整数（包括对照输入和最坏情况下的输入），给出id[]和sz[]数组的内容以及访问数组的次数。

1.5.5 在一台每秒能够处理109条指令的计算机上，估计quick-find算法解决含有109个触点和106条连接的动态连通性问题所需的最短时间（以天记）。假设内循环for的每一次迭代需要执行10条机器指令。

1.5.6 使用加权quick-union算法完成练习1.5.5。

1.5.7 分别为quick-find算法和quick-union算法实现QuickFindUF类和QuickUnionUF类。

1.5.8 用一个反例证明quick-find算法中的union()方法的以下直观实现是错误的：

public void union(int p, int q)
{
    if (connected(p, q)) return;
    // 将p的分量重命名为q的分量
    for (int i = 0; i ＜ id.length; i++)
        if (id[i] == id[p]) id[i] = id[q];
    count--;
}

1.5.9 画出下面的id[]数组所对应的树。这可能是加权quick-union算法得到的结果吗？解释为什么不可能，或者给出能够得到该数组的一系列操作。

1.5.10 在加权quick-union算法中，假设我们将id[find(p)]的值设为q而非id[find(q)]，所得的算法是正确的吗？

答：是，但这会增加树的高度，因此无法保证同样的性能。

1.5.11 实现加权quick-find算法，其中我们总是将较小的分量重命名为较大的分量的标识符。这种改变会对性能产生怎样的影响？

提高题

1.5.12 使用路径压缩的quick-union算法。根据路径压缩修改quick-union算法（请见1.5.2.3节），在find()方法中添加一个循环来将从p到根节点的路径上的每个触点都连接到根节点。给出一列输入，使该方法能够产生一条长度为4的路径。注意：该算法的所有操作的均摊成本已知为对数级别。

1.5.13 使用路径压缩的加权quick-union算法。修改加权quick-union算法（算法1.5），实现如练习1.5.12所述的路径压缩。给出一列输入，使该方法能够产生一棵高度为4的树。注意：该算法的所有操作的均摊成本已知被限制在反Ackermann函数的范围之内，且对于实际应用中可能出现的所有N值均小于5。

1.5.14 根据高度加权的quick-union算法。给出UF的一个实现，使用和加权quick-union算法相同的策略，但记录的是树的高度并总是将较矮的树连接到较高的树上。用算法证明N个触点的树的高度不会超过其大小的对数级别。

1.5.15 二项树。请证明，对于加权quick-union算法，在最坏情况下树中每一层的节点数均为二项式系数。在这种情况下，计算含有N=2n个节点的树中节点的平均深度。

1.5.16 均摊成本的图像。修改你为练习1.5.7给出的实现，绘出如正文所示的均摊成本的图像。

1.5.17 随机连接。设计UF的一个用例ErdosRenyi，从命令行接受一个整数N，在0到N-1之间产生随机整数对，调用connected()判断它们是否相连，如果不是则调用union()方法（和我们的开发用例一样）。不断循环直到所有触点均相互连通并打印出生成的连接总数。将你的程序打包成一个接受参数N并返回连接总数的静态方法count()，添加一个main()方法从命令行接受N，调用count()并打印它的返回值。

1.5.18 随机网格生成器。编写一个程序RandomGrid，从命令行接受一个int值N，生成一个N×N的网格中的所有连接。它们的排列随机且方向随机（即（p q）和（q p）出现的可能性是相等的），将这个结果打印到标准输出中。可以使用RandomBag将所有连接随机排列（请见练习1.3.34），并使用如右下所示的Connection嵌套类来将p和q封装到一个对象中。将程序打包成两个静态方法：generate()，接受参数N并返回一个连接的数组；main()，从命令行接受参数N，调用generate()，遍历返回的数组并打印出所有连接。

1.5.19 动画。编写一个RandomGrid（请见练习1.5.18）的用例，和我们的开发用例一样使用UnionFind来检查触点的连通性并在处理的同时用StdDraw将它们绘出。

1.5.20 动态生长。使用链表或大小可变的数组实现加权quick-union算法，去掉需要预先知道对象数量的限制。为API添加一个新方法newSite()，它应该返回一个类型为int的标识符。

实验题

1.5.21 Erdös-Renyi模型。使用练习1.5.17的用例验证这个猜想：得到单个连通分量所需生成的整数对数量为～1/2NlnN。

1.5.22 Erdös-Renyi模型的倍率实验。开发一个性能测试用例，从命令行接受一个int值T并进行T次以下实验：使用练习1.5.17的用例生成随机连接，和我们的开发用例一样使用UnionFind来检查触点的连通性，不断循环直到所有触点均相互连通。对于每个N，打印出N值和平均所需的连接数以及前后两次运行时间的比值。使用你的程序验证正文中的猜想：quick-find算法和quick-union算法的运行时间是平方级别的，加权quick-union算法则接近线性级别。

1.5.23 在Erdös-Renyi模型下比较quick-find算法和quick-union算法。开发一个性能测试用例，从命令行接受一个int值T并进行T次以下实验：使用练习1.5.17的用例生成随机连接。保存这些连接并和我们的开发用例一样分别用quick-find算法和quick-union算法检查触点的连通性，不断循环直到所有触点均相互连通。对于每个N，打印出N值和两种算法的运行时间的比值。

1.5.24 适用于Erdös-Renyi模型的快速算法。在练习1.5.23的测试中增加加权quick-union算法和使用路径压缩的加权quick-union算法。你能分辨出这两种算法的区别吗？

1.5.25 随机网格的倍率测试。开发一个性能测试用例，从命令行接受一个int值T并进行T次以下实验：使用练习1.5.18的用例生成一个N×N的随机网格，所有连接的方向随机且排列随机。和我们的开发用例一样使用UnionFind来检查触点的连通性，不断循环直到所有触点均相互连通。对于每个N，打印出N值和平均所需的连接数以及前后两次运行时间的比值。使用你的程序验证正文中的猜想：quick-find算法和quick-union算法的运行时间是平方级别的，加权quick-union算法则接近线性级别。注意：随着N值加倍，网格中触点的数量会乘4，因此平方级别的算法的运行时间会变为原来的16倍，线性级别的算法的运行时间则变为原来的4倍。

1.5.26 Erdös-Renyi模型的均摊成本图像。开发一个用例，从命令行接受一个int值N，在0到N-1之间产生随机整数对，调用connected()判断它们是否相连，如果不是则调用union()方法（和我们的开发用例一样）。不断循环直到所有触点均相互连通。按照正文的样式将所有操作的均摊成本绘制成图像。