共计 5026 个字符，预计需要花费 13 分钟才能阅读完成。
前言
如果能够科学上网，英文水平良好，建议登入 cousera 进行学习。平台上有完整的作业提交平台，对提交的作业有详细的性能诊断和反馈；有课程各种资源；有课程讨论。在课程提问区提问还会收到导师的回答。链接：Algorithms, Part IAlgorithms, Part II
《算法》第四版：testbook 链接(英文)：https://algs4.cs.princeton.ed…
主要内容
并查集是一种树形的数据结构，通过这种数据结构能够有效处理不相交集合间的合并 (union) 及查询 (find) 问题。比如动态连通性问题。这种数据结构主要涉及两个操作：Find：查询元素属于哪一个子集。此操作还可以用来确定两个元素是否属于同一子集。Union：将两个子集合并成到一个集合中。
1. 动态连通性问题(dynamic connectivity)
动态连通性的应用很广泛：比如网络诊断：网络中的两台计算机是否连通，社交网络中的两个人是否存在交集，芯片中的电路元件连通性等等。场景：对象数码照片：像素网络：计算机社交网络：人 … 在编程中我们会对所有这些不同类型的对象进行简单的编号（0 — N-1），这样方便利用整数作为数组的索引号，快速地访问每个对象的相关信息，还可以忽略与并查集问题不相关的很多细节。
1.1 建立问题模型
给定一个有 N 个性质相同的对象的集合问题大体上所需要的基本操作：
连通（Union）：两个对象间可以连通
连通性的查询（Find/connected）：查询两个对象之间是否有连通路径
如下图，通过 Union(x,y)命令给若干对象之间建立连通路径；通过 connected(x,y)命令查看两个对象是否连通。
我们的任务就是对于给定的对象集合高效地实现这两个命令。因为合并命令和连通命令交叉混合，所以我们还有一个任务是我们的解决方案能支持大量对象和大量混合操作的高效处理。
1.2 提取连通性质的抽象性
1.2.1 假设“连接到（is connected to）”是一个具有下边关系性质的等价关系：那么它会有如下一些性质：
反身：每个对象都能连接到自己（p is connected to p）
对称：如果 p 与 q 连通，那么 q 也与 p 连通
传递：如果 p 与 q 连通，q 与 r 连通，那么 p 与 r 连通
这些性质都是直观自然的。明确了这些等价关系后，下面给出“连通分量”的定义。
1.2.2 连通分量（connected components）
有了等价关系后，一个对象和链接的集合就分裂为子集，这些子集就为连通分量。连通分量是互相连接对象的最大集合，并且连通分量之间并不连通。如下图左边，有 3 个连通分量。我们的算法通过维护连通分量来获得效率，并使用连通分量来高效地应答接收的请求。
有了连通分量的概念后，并查集（即动态联通问题）要实现的操作有:
Find 查找: 查找检查两个对象是否在相同的连通分量中
Union 合并命令：将包含两个对象的连通分量合并为一个子集（一个连通分量）。如下图。
1.3 Union-find 数据类型（API)
从之前的讨论我们得到了一个数据类型，在编程的概念中，它是为了解决问题我们想要实现的方法和规范。在 Java 的模型中，创建一个类来表示这些方法和规范。其中包含：
构造函数：参数是对象的数量，根据对象的数量建立数据结构
两个操作：a) 实现合并；b) 连接超找，返回一个布尔值（逻辑变量：真 / 假）
在实现算法的过程中，应该明确算法在以下的情况下也必须高效：
对象和操作的数量都可能是巨大的
合并和连接的混合操作也会非常频繁
在处理更深层的问题之前，通过设计一个测试客户端用于检查 API，确保任何一种实现都执行了我们希望他执行的操作。如下图，客户端从标准输入（tinyUF）中读取信息。首先读取“10”这个整数，表示要处理的对象的数量，并创建一个 UF 对象。然后只要标准输入中还有输入，客户端将从输入读取两个整数，如果他们没有连通，将他们连通并输出。否则忽略这条输入。
2. 实现动态连通性问题的算法
也可以说就是实现并查集的算法。这些算法的目的并不是给出两个对象的连通路径是什么，而是回答是否存在这么一条路径。虽然给出两个对象相连的路径也回答了是否连通的问题，但是于我们的目的而言不是直接契合，效率也不高。使用并查集数据结构是一个不错的策略。
实现动态连通性问题的算法有：
quick-find 快速查找（QF）
quick-union 快速合并（QU）
Weighted quick-union 加权优化（WQU）
Quick union with path compression 路径压缩优化（QUPC）
两种优化可以结合一起使用，以下简称 ”WQUPC”, 即 weighted QU + path compression
2.1 quick-find
快速查找算法也称为“贪心算法”。（简单来说贪心算法就是在对问题求解时总是作出当前看来是最好的选择，只得出在某种意义上的局部最优解，不一定能得到整体最优解）
2.1.1 Qinck-find 简介
Qinck-find 数据结构：
简单的对象索引整数数组 id[](size = n)(具体来说就是当且仅当两个对象 p 与 q 是在数组中的 id 一样，那么他们即为连通)如图：0,5,6 在一个连通分量；1,2,7 在一个连通分量；3,4,8,9 连通
由此：
Find：检查 p 和 q 是否 id 值相等 Union：合并两个给定对象的的两个连通分量，即需要将与给定对象之一（p）有相同 id 的所有对象的 id 值都变为另一个给定对象（q）的 id 值如图经过 union(6,1), 通过合并 6 和 1,6 所在的连通分量中的所有对象（0,5,6）的 id 值都变为 1 的 id 值（1）这个算法的主要问题是当进行合并操作是，遇往后，需要改变 id 值的操作就越多。
2.1.2 Java 实现：
a) 构造器：建立一个私有化整数数组，并将对应索引的数组项设为索引值 b) 连通判断：两个数组项的 id 值是否相等 c) 合并操作：取出两个参数的 id 值，遍历整个数组，找到同第一个参数 id 值相同的所以 id 项，并将他们都赋值成第二个参数的 id 值。
具体代码实现：QuickFindUF.java
2.1.3 性能分析
衡量因子：代码需要访问数组的次数增长量级构造函数初始化和合并操作时都需要遍历整个数组，所以他们必须以常数正比于 N 次访问数组（增长量级为 N）查找的操作很快，只需要进行常数次比较（增长量级为 1）
算法的特点是查找很快，但是合并的代价太大，如果需要在 N 个对象上进行 N 次合并操作，访问数组就需要 N 的平方次增长量级的操作，这是不合理的。平方量级的时间太慢。对于大型问题不能接受平方时间的算法。随着计算机变得更快，平方时间算法实际会变得更慢，简单来说，假如计算机每秒能进行几十亿次的操作，这些计算机的主内存中有几十亿项，大约一秒钟的时间我们就可以访问主内存所有的项，现在希望算法对几十亿的对象进行几十亿的操作，快速查找算法需要访问数组大约 10 的 18 次方次，大概是 30 多年的计算时间。
2.2 quick-union
快速查找对于处理巨大问题太慢，所以第一个尝试是使用快速合并算法进行替换。快速合并的算法设计采用了所谓的“懒策略”，即尽量避免计算直到不得不进行计算。
2.2.1 Quick-union 简介
Quick-union 数据结构
大小为 N 的整数数组 id[]（size = N）这里的数组看做是一片森林（即一组树的集合），数组中的每一项包含它在树中的父节点。下图可以看出 3 的父节点是 4, 4 的父结点是 9，9 的父节点是它自身，也就是 9 是这颗树的父节点。从某个对象出发，一路从父节点向上就能找到根节点。
由此：
Find：查找两个对象（p & q）的根节点是否相等 Union：合并两个对象的连通分量，即把 p 的根节点的值设为 q 的根节点的值。如图，union(3,5) 即把 3 的根节点 (9) 的 id 值设为 5 的根节点 (6) 的 id 值。由此，3 所在的连通分量与 5 所在的连通分量进行了合并。
可以看出合并两个连通分量只需要改数组中的一个值，但查找根节点会需要多一些操作。
2.2.2 Java 实现：
a) 构造器与 Quick-find 相同 b) 私有方法 root()通过回溯实现寻找根节点 c) 通过私有方法实现查找操作（是否连通操作）。通过判断两个对象的根节点是否相同即得出返回 d) 合并操作就是找到两个对象的根节点，并将第一个根节点的 id 值设为第二个对象根节点的 id 值
详细实现：QuickUnionUF.java
2.2.3 性能分析：
衡量因子：代码需要访问数组的次数增长量级快速合并的算法依旧很慢。快速查找的缺点在于树可能太高，这样对于查找操作的代价太大，最坏的情况需要 N 次数组访问才能找到某个对象的根节点。（合并操作的统计也包含了查找跟的操作）
3 quick-union 算法改进
3.1 加权
QF 和 QU 都不能支持巨大的动态连通性问题，一种有效的改进办法：加权 Weighted quick-union 之前说到了 QU 的缺点就是因为树太高会引起查找操作代价巨大，那么在实现 QU 算法的时候执行一些操作避免得到很高的树就是改进的一个思路。QU 算法在合并两颗树的时候可能会把大树放在小树的下边，如此树会变高。为了避免合并后导致更高的树，让小树的根节点指向大树的根节点。由此保证所有的对象不会离根节点太远。可以通过加权的方式可以实现。
WQU:
跟踪每棵树中对象的个数
将小树（对象所在的连通分量里的元素个数较少一方）的根节点设为大树的根节点的子节点
Java 实现
数据结构在 QU 的基础上添加一个额外的数组 size[i] 记录以该对象为根节点的树中的对象个数
Find: 同 QU 一样，只需要检查根节点是否相同 Union：通过 size[i] 先检查两颗树的大小，然后将小树的根节点设为大树的根节点，同时更新合并后连通分量中根节点项的 size 数组项的值
完整实现：WeightedQuickUnionUF.java
性能分析
运行时间 Find：与结点在树中的运行时间成正比 Union：给出根节点后花费常量时间
命题树中任意结点的深度上限为 lgN(此 lg 以 2 为底数)
证明理解这个命题的关键在于观察节点（此为 X 节点）的深度到底是在何时会增加 a) 只有当 T2 的尺寸 >=T1 的尺寸的时候，T1 和 T2 才会合并为一个连通分量，此时 T1 的深度（depth）才会增加 b) 合并后 T1 的大小至少是原来的 2 倍，由此粗略估计，x 的深度每增加 1，则 x 所在的集合的大小变为原来的 2 倍 c) 如果整个集合的大小为 N，那么 x 所在的集合大小最大尺寸只能为 N，那么从 x = 1 开始，有 1 *2^depth=N –> depth = lgN 即树中任意节点的深度最多为 lgN
三种算法的性能对比
如果 N 是 100 万，则 lgN=20；如果 N 是 10 亿，lgN=30。加权的处理在代码上并不需要多少的修改，可是性能上却取得了很大的提升。
3.2 路径压缩
在经过加权处理后，还可以更进一步优化这个算法。此为添加路径压缩 Quick union with path compression 的操作。在试图寻找包含给定节点的树的根节点时，我们需要访问从该节点到根节点路径上的每个节点。那么，于此同时我们可以将访问到的所有节点的根节点顺便移动设置为他所在的树的根节点。这需要付出常数的额外代价。如图：当我们找到 P 的根节点后，把 9,6,3 的根节点都设为 0（1 的根节点已经是树的根节点）：
变为
这里做的改变是：将路径上的每个节点指向它在路径上的祖父节点，这种实现并没有把树完全展平，但在实际应用中两种方式都超不多一样好。
将树完全展平：find(int p) 方法回溯一次路径找到根节点，然后再回溯一次将树展平，参考：QuickUnionPathCompressionUF.java
性能分析
以证明：有 N 个对象，M 个合并与查找操作的任意序列，需要访问数组最多为 c(N + M lg* N)次。lg*N 是使 N 变为 1 所需要的对数的次数，叫迭代对数函数。在真实世界中可以认为 lg* N 是一个小于 5 的数。
这个证明可以不用深究，两种优化的代码实现参考：WeightedQuickUnionPathCompressionUF.java
通过 WQUPC 的优化，之前的例子，假如要对 10 亿个对象进行 10 亿个操作，QF 需要 30 年，现在只需要大概 6 秒。
课后巩固（折日更新）
Interview Questions 面试问题
Programming Assignment: Percolation 编程练习
IDE 本人使用 IntelliJ IDEA, jdk8 需要使用的 jar 包：
git 地址：
