数据结构其二 并查集
前言
看了下时间距离上一篇 线性表 的文章已经过去了半年了……
虽然这段时间倒也没有停止学习，但也由于各种原因总之是一直拖着没产出。所幸最近因为一些机缘巧合杠上了并查集，趁热打铁的赶紧把这篇文章写了。
考虑到自己学习这些东西的过程其实也不是线性的（总是忍不住东搞搞西搞搞），所以这篇就以更加轻松的方式来简单分享一下最近对并查集这种数据结构的学习好了。
0.1 关于并查集
其实早在我写 数据结构其一 线性表 一文之前就已经自己写了一个简单的并查集类实现 yuchiXiong/data-structure-and-algorithm/commit/ae60aa61c4e4581be3b5508e8887f1f7331b53e7 了，当时刚开始看 《算法（第 4 版）》，书的第一章结尾用并查集做了简单的案例。
打开这段代码的时候，就发现文件头写了三行注释，很好的说明了我当时写完这个代码的心境：
/**
* ! 对于这个数据结构的疑问
* 1. 给定的数据一定是有序的吗？find 函数越界问题
* 2. 使用场景
*/
另外从代码中也发现了不少 Bug，反思了一下觉得自己一直不肯写这篇的一大原因可能是没有理解。
0.2 Why again?
故事要从本月 18 号的 LeetCode 每日一题 LC27. 最大人工岛 说起了。
作为一个算法废人，我一直是 “困难唯唯诺诺，简单重拳出击” 的摆烂心态，此外我一直坚信一件事情：
当你看完一个算法题 5 分钟内一点思路都没有，那大概率是因为你还不具备解决该类问题的知（suan）识（fa）储（tao）备（lu），而非你脑子有问题/狗头
但好巧不巧，在 LeetCode 数据结构入门的专题训练中，有一道 LC695. 岛屿的最大面积。
这道题的思路很简单，由于每一个岛屿单元所处的岛屿面积一定等于它上下左右四个方向邻接单元上的岛屿面积之和，很容易写出 DFS 的代码模板。
当然，要记得定义递归的终止条件，即如果当前单元为 0 时，意味着已经遍历到海洋了，不需要继续了。另外为了防止重复遍历，代码还对已经遍历过的岛屿进行了标记。
代码见 yuchiXiong/data-structure-and-algorithm/commit/63659b20643b1e6b7b8bfb59efd283d21257868a
显而易见的事情是 LC27. 最大人工岛 的一种暴力解法就是尝试将地图上的每一片海洋都改成岛屿然后求得最大岛屿面积，最终得到的最大值就是题解。
虽然不能保证效率，但能暴力解决的问题都不是问题/再次狗头，开整。
在经过了一段时间的死嗑之后，我写下了这段代码：
/**
* @param {number[][]} grid
* @return {number}
*/
const largestIsland = function (grid) {
let count = 2;
let max = maxAreaOfIsland(grid, count++);
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
// 跳过岛屿，我们只对海洋做操作
if (grid[i][j] !== 0) {
continue;
}
// 尝试检测当前海洋的四面是否存在岛屿，如果四面都没有岛屿，则当前人工岛面积为 1
if (tryDFS(grid, i, j) === 0) {
max = max < 1 ? 1 : max;
continue;
}
// 修改当前单元 海洋->岛屿 并求得最大岛屿面积
const origin = grid[i][j];
grid[i][j] = 1;
const cur = maxAreaOfIsland(grid, count++);
max = max < cur ? cur : max;
grid[i][j] = origin;
}
}
return max;
};
/**
* @param {number[][]} grid
* @param {number} count
* @return {number}
*/
var maxAreaOfIsland = function (grid, count) {
let max = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (grid[i][j] === 1) {
max = Math.max(max, dfs(grid, i, j, count));
}
}
}
return max;
};
/**
* @param {number[][]} grid
* @param {number} i
* @param {number} j
* @param {number} count
* @return {number}
*/
const dfs = (grid, i, j, count) => {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return 0;
if (grid[i][j] === 0 || grid[i][j] === count) return 0;
grid[i][j] = count;
return 1
+ dfs(grid, i - 1, j, count)
+ dfs(grid, i + 1, j, count)
+ dfs(grid, i, j - 1, count)
+ dfs(grid, i, j + 1, count);
}
/**
* 返回当前单元四个方向范围内的岛屿面积总和
* @param {number[][]} grid
* @param {number} i
* @param {number} j
* @return {number}
*/
const tryDFS = (grid, i, j) => {
return (i >= 1 ? (grid[i - 1][j]) : 0)
+ (i < grid.length - 1 ? grid[i + 1][j] : 0)
+ (j >= 1 ? grid[i][j - 1] : 0)
+ (j < grid[i].length - 1 ? grid[i][j + 1] : 0);
}
其中maxAreaOfIsland函数是直接复制的 LC695. 岛屿的最大面积 的答案。
需要解释的几点：
- 前面提到在 DFS 过程中会标记已经遍历过的岛屿，也就是说每一次
maxAreaOfIsland后grid数组中的岛屿标识会由 1 变成 2，为了使程序能够继续执行第二轮maxAreaOfIsland，需要将grid数组复原，但这样的又会增加相当大的开销，于是最终我将函数改成了上面的版本，每次传入一个count变量来标识轮次，这样 DFS 也能重复执行了； - 为了尽可能提高效率，程序首先跳过了岛屿单元，然后对四周都没有岛屿的单元做了提前处理，详见注释；
在完成了一些简单的优化后，一些之前不能通过的 case 也能跑出一个可以接受的执行时间了，但最终还是卡在了 case70 上。
在对这个 case 进行了简单的分析之后我发现：
- 这是一个 417*417 规模的数组；
- 岛屿和海洋的数量几乎相同；
- 岛屿与海洋的分布稀疏；
不难发现上述优化策略很难产生效果。
本来这题就该到此为止了，毕竟死磕没有意义，又不能说服自己 “答案是对的，只是超时了而已”。
然而接下来一个不经意的操作，让我发现了这一题的相关标签中赫然写着一个并查集。
如果是我没有接触过的东西那倒也罢了，一个我手写过的东西为什么能把我困住？
1. 并查集
既然这是一篇分享并查集的博客，那么还是有必要介绍一下并查集的。
从字面上来看，并查集是一种集合数据结构，它主要定义了联合（union）和查询（find）两种操作，因此很多时候也被叫做 UnionFind。
wiki：并查集 查询：查询某个元素属于哪个集合，通常是返回集合内的一个 “代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。 合并：将两个集合合并为一个。 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。
并查集定义的查询操作能够快速的反应集合中两个元素的连通性，而合并/联合操作则可以将集合中的两个元素连通，它被广泛的应用在动态连通性问题中。
对并查集应用的一个简单的例子就是族谱，设想我们如何判断两个人 A 和 B 是否来自于同一个家族？
一个简单的方法就是向上溯源，如果 A 和 B 的长辈中有同一人，则我们可以认为这两个人来自同一个家族。
将问题的规模扩展到三人，如果我们当前已经知晓 A 和 B 来自同一个家族，则我们只需要证明第三人 C 与 A/B 任意一人来自同一个家族，就可以认为 C 与另外一人来自同一个家族。
由此我们可以得到并查集中元素的三个重要性质：
- 自反性，A 和 A 是连通的；
- 对称性，如果 A 和 B 是连通的，那么 B 和 A 也是连通的；
- 传递性，如果 A 和 B 是连通的且 B 和 C 是连通的，那么 A 和 C 也是连通的。
2. 并查集的实现
只提概念不谈实现是没有意义的。
并查集的主要操作有两个，查询和合并，实现这两个方法是实现并查集最重要的部分，除此之外在不同版本的并查集实现中往往存在着各种 API 定义上的差异，但数据结构本身是用来解决程序问题的，如果拘泥于 API 形式亦是有问题的，这个问题后面还会再提到。
在前面的例子里我们提到一个问题：如何判断两个人 A 和 B 是否来自于同一个家族？
给出的答案很简单：如果 A 和 B 的长辈中有同一人，则我们可以认为这两个人来自同一个家族。
在并查集的实现中我们亦可以这样做。
在开始之前，我们要简单分析一下上面的描述，在这个系统里存在一种父子关系，且多个元素可能有一个共同的根元素，很显然，没有比树更合适的数据结构了。
当然，并查集具有检测两个元素是否连通的能力，也就意味着在并查集中可能存在多个没有交集的树，因此我们更进一步的表达为森林这样一种数据结构。
2.1 构建一个并查集
实现一个基本的并查集需要一个合适的变量来存储森林这种结构，前面在 线性表 一文中提到过，无论逻辑呈现什么样的结构，在计算机存储时都只有线性存储与链式存储两种。这里一样拥有这种自由，《算法（第 4 版）》 中使用了顺序结构。
使用顺序表实现森林时首先将并查集中的所有元素的值作为 key 创建一个顺序表（姑且不去讨论元素值类型与顺序表下标数值类型转换的问题），在初始化时它的值是它自身，即当前元素仅与自己连通。
而后在每次进行合并操作时，我们会修改元素的指向，类似下面这样
trees[targetA] = targetB;
此时意味着元素 A 的父元素是元素 B，同时以意味着元素 A 与元素 B 连通。
2.1 查询
就像家族关系的例子一样，判断两个元素是否连通，只需要判断它们是否具有一个公共的根元素即可。
基于上面 2.1 构建的存储结构，找到根元素只需要不断的向上查找，一直找到到某一个自身与父元素相等的节点，这个元素就是整个树的根元素。
function getRootNode(target) {
while (trees[target] !== target) {
target = trees[target];
}
return target;
}
接下来的判断就简单了，当getRootNode(elementA)与getRootNode(elementB)相同时，很显然两个元素是连通的。
2.2 合并
由上面的逻辑要实现合并也非常简单，不过在进行两个元素的合并之前首先要判断是否连通，如果元素 A 和 B 已经连通了，就没有必要浪费时间了。
要进行两个元素的连通，只要把其中一方的父元素指向另一方就可以了，不过通常来说我们并不能得知当前正在进行连通的两个元素是独立的还是处于一个树中，贸然修改其指向有可能会使它脱离原来的树，因此我们应该对两个树的根元素进行操作。
简单的参考代码如下：
function unionNode(a, b) {
const parentA = getRootNode(a);
const parentB = getRootNode(b);
if (parentA === parentB)
return;
parent[parentB] = parentA;
}
2.3 更进一步
基本的实现其实到这里就已经够了，但设想这样一种情况：
const uf = new UnionFind();
uf.union(1, 2);
uf.union(3, 2);
uf.union(4, 3);
uf.union(5, 4);
尝试在纸上画出这组 case 的连通过程，很容易发现由于每一次构建的过程中的元素 A 都是一个指向自身的只有一个节点的树，导致合并以后构建的树实际退化成了单链表。对于树中任意一个节点要找到它的根元素，单链表的效率一定是低于一颗合理排布的树的。
优化策略本质上是要维护树的平衡性，我们只需要在连接的过程中把更小的那颗树连接到更大的那棵树的根节点上，就可以尽可能保证树的平衡性，也可以避免上述极端情况的发生。不过要实现这一步，我们需要增加一个类变量来记录每一颗树的大小，以及在每一次连通的时候对树的大小进行累加。
相比二叉树，一个树可以拥有的子节点数是没有限制的。如果一颗树除根元素以外的所有元素均指向同一个根元素，即这棵树只有两层，那么除根元素以外的任意一个节点找到它的根元素都只需要向上查找一次。
基于这个假设，我们可以在查找的过程中进行路径压缩，使树变得更加扁平化。
理想情况下，所有元素都应该直接连接在根元素下作为根元素的子节点，下面代码巧妙的实现了它：
function getRootNode(target) {
if (this.trees[target] !== target) {
this.trees[target] = this.getRootNode(this.trees[target]);
}
return this.trees[target];
}
为什么要在查找的过程中而不是在连通的过程中修改树的结构？
理想情况下，我们希望每个节点都直接链接到它的根节点上，但我们又不想像 quick-find 算法那样通过修改大量链接做到这一点。我们接近这种理想状态的方式很简单，就是在检查节点的同时将它们直接链接到根节点。这种方法乍一看很激进，但它的实现非常容易，而且这些树并没有阻止我们进行这种修改的特殊结构：如果这么做能够改进算法的效率，我们就应该实现它。 ————《算法（第 4 版）》
至此我们实现了并查集数据结构最重要的部分，可以看到的是它的代码并不复杂，但又很好的给出了一个解决连通性问题的方案。 代码参考 UnionFind.cpp
3. 回到岛屿上
我自然没有忘记小岛上还有问题等着我解决。
并查集中的每一个连通元素整体都被称为一个连通分量，当一个并查集中的所有元素都连通时，这个并查集只存在一个连通分量。
回到 LC695. 岛屿的最大面积 的问题中，如果把岛屿的每一个单元（即grid二维数组的每一个元素）看作并查集中的一个元素，则基于这组元素构建的并查集中，一定包含连通分量数量 N 个岛屿，其中最大面积的岛屿实际上就是最大连通分量的大小。
去除了 DFS 的代码基于并查集进行了重新实现： yuchiXiong/data-structure-and-algorithm/commit/445c5d669c468667ddfed32b921759cd586a815c
不得不吐槽的一件事情：代码真的长了好多……
不过依然有一些地方值得留意：
- 在这一版代码中，不再直接使用顺序表来存储父节点信息，而是通过 Hash 表替代，这样做的好处在于可以接受更多类型的 key；
- 把每一个元素在二维数组扁平化以后的序号作为并查集的元素，
grid[i][j]在并查集中的 key 为(i - 1) * grid.length + j；
在解决这个问题时，并查集的优点并没有那么明显，一定程度上来说代码还显得十分啰嗦，而在解决 LC27. 最大人工岛 问题时，并查集带来的收益就要明显的多了。
使用地图信息构建一次并查集以后，我们可以清晰的得知如下信息：
- 当前地图中的岛屿数量；
- 当前地图中的每一个单元所处岛屿的面积；
- 当前地图中任意两个岛屿单元是否处于同一个岛屿中；
利用这些信息，我们只需要遍历地图，在每一个海洋单元上计算它的上下左右四个单元所处的岛屿面积之和，然后找到最大值即可得到题解。
当然，如果上下左右四个邻接单元有位于同一个岛屿的单元，我们只计算一次。
yuchiXiong/data-structure-and-algorithm/commit/d8bbe157f7a07d881e7b06cee94e5a3a25a70d0a
至此，两道 LeetCode 问题也圆满的解决了。
4. 最后说两句
重新审视了去年实现的代码，除了注释中的疑问外还有不少的 bug，于是趁着这个机会也一并修复了 Github: yuchiXiong/data-structure-and-algorithm/commit/e68b19772b57eaac4e49dba89f783266f0f9eef3。
并查集是用来处理元素连通性问题的数据结构，它仅仅关注元素与元素之间的连通问题，不关心森林用顺序存储还是链式存储实现。在合适的时间选择合适的方法才是最重要的。
在查找一些并查集代码实现的案例时，会发现不同人写下的代码是不同的，有的初始化时传递了连通分量来进行，有的仅在使用时创建并进行自连通，但本质上这些都是根据实际问题不同而自由发挥的。
另外一件值得一提的事情是，在尝试找一些编程语言自带的 DisjointSet 时，发现 Ruby 的 Set 类中提供了一个 disjoint?方法，当两个集合有相同的元素时，该方法返回 false，反之则返回 true。Set 是一种不会出现重复元素的数据结构，并查集同样是没有交集的森林，如果把森林中的每个树看作是一个 Set，仅仅一个函数就可以以完整的实现并查集的功能了。一方面我十分感叹竟然可以通过如此简单的方式实现并查集，同时另一方面则是更多的引人深思，数据结构的 API 设计本就没有标准可言。