算法(4th ed)(202):基础——案例研究:union-find 算法 7.1.3

阅读数:4 2019 年 11 月 9 日 15:51

算法(4th ed)(202):基础——案例研究:union-find 算法 7.1.3

(动态连通性:数学集合)

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

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

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

算法(4th ed)(202):基础——案例研究:union-find 算法 7.1.3

图 1.5.2 中等规模的连通性问题举例(625 个触点,900 条边,3 个连通分量)

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

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

表 1.5.1 union-find 算法的 API

public class UF
             UF(int N)以整数标识(0 到 N1)初始化 N 个触点
      void   union(int p, int q)pq 之间添加一条连接
       int   find(int p)p(0 到 N1)所在的分量的标识符
   boolean   connected(int p, int q)如果 pq 存在于同一个分量中则返回 true
       int   count()连通分量的数量

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

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

  • 定义一种数据结构表示已知的连接;
  • 基于此数据结构实现高效的 union()find()connected()count() 方法。

众所周知,数据结构的性质将直接影响到算法的效率,因此数据结构和算法的设计是紧密相关的。API 已经说明触点和分量都会用 int 值表示,所以我们可以用一个以触点为索引的数组id[] 作为基本数据结构来表示所有分量。我们将使用分量中的某个触点的名称作为分量的标识符,因此你可以认为每个分量都是由它的触点之一所表示的。一开始,我们有 N 个分量,每个触点都构成了一个只含有它自己的分量,因此我们将id[i] 的值初始化为 i,其中 i0N-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");
}
}

复制代码
% java UF < tinyUF.txt
4 3
3 8
6 5
9 4
2 1
5 0
7 2
6 1
2 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 规模类似的输入。

复制代码
% more tinyUF.txt
10
4 3
3 8
6 5
9 4
2 1
8 9
5 0
7 2
6 1
1 0
6 7
% more mediumUF.txt
625
528 503
548 523
...
900 条连接
% more largeUF.txt
1000000
786321 134521
696834 98245
...
200 万条连接

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

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

评论

发布