用并查集解决岛屿数量：连通性、路径压缩与工程实践

1. 一个高频面试题引出的"数据机构"之争：岛屿数量

1.1 题目本身到底在考什么

LeetCode 200"岛屿数量"，题目描述非常简短：给你一个由'1'（陆地）和'0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

很多第一次刷题的人会以为这题就是考 DFS（深度优先搜索），因为递归遍历'1'周围四个方向，遇到'1'就淹没成'0'，循环统计调用次数，似乎几分钟就写完。确实，DFS 和 BFS 都能 AC，而且代码短。但真正去大厂面试时，面试官常常会追加一句："你先别急，能不能用并查集做一遍？"

这道题能流传得这么广，恰恰因为它可以同时考察三种核心思维：写的 DFS 考递归熟练度，写的 BFS 考队列使用，写并查集才是真正考"你会不会用数据结构抽象连通性问题"。

1.2 为什么这种"网格连通"问题天然适合并查集

并查集（Union-Find）解决的是动态连通性问题，也就是"两个元素是否属于同一个集合"以及"把两个集合合并成一个"。把网格里的每一块陆地看成一个个独立的节点，相邻的陆地之间建立连接关系，那么所有互相连通的陆地最终会归属到同一个集合里。一个集合对应一座岛屿，统计集合的个数，就是统计岛屿数量。

这个思路最优雅的地方在于：DFS 是靠递归隐式维护连通性，而并查集是显式地维护"谁和谁连在一起"。DFS 适合回答"从某个点出发能到达哪些点"，并查集则更适合回答"任意两个点是不是同一个集合里的"。岛屿数量这道题要的是"总共有几个连通块"，并查集做这个统计几乎不需要额外思考，只要维护一个count变量，每次合并成功就减一，最后剩下的就是答案。

2. 并查集的基础框架：三样东西缺一不可

2.1 数据结构的核心字段

一个朴素的并查集要维护三个字段：

int[] parent; // 每个节点的父节点，初始时指向自己 int[] rank; // 树的秩（高度上界），用于合并时保持平衡 int count; // 当前连通分量个数，即集合总数

parent是并查集的主干，find(x)不断向上找，直到找到parent[x] == x的那个节点，它就是集合的代表元。count是这道题里最关键的变量，初始化为陆地总数，每次合并两个不同集合时count--，最后count就是岛屿数。

2.2 find 操作：路径压缩的两种写法

find的作用是找到元素所在集合的根节点，同时做路径压缩。路径压缩的目的是把树的形状压扁，让每个节点尽量直接指向根，这样后续查找几乎可以做到 O(1)。

递归版本的find是最容易记忆的写法：

public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; }

这里parent[x] = find(parent[x])就是路径压缩的体现：在递归返回的过程中不断把中间节点直接挂到根节点上。注意，虽然递归在极端情况下（比如数深度特别大）可能有栈溢出的风险，但配合路径压缩后树的高度很小，实际应用中很少出问题。如果你实在担心，可以写迭代版本：

public int find(int x) { int root = x; while (parent[root] != root) { root = parent[root]; } // 第二遍循环，把路径上所有节点直接指向根 while (parent[x] != x) { int next = parent[x]; parent[x] = root; x = next; } return root; }

两种写法都可以，我更推荐递归版本，代码短、可读性强，面试时也容易当场写对。

2.3 union 操作：按秩合并到底"秩"什么

union的核心逻辑很简单：先找两个节点各自所在集合的代表元，如果代表元相同，说明本来就在一个集合里，什么都不用做；如果不同，就把一棵树的根接到另一棵树的根上。问题在于谁接谁，如果随便接，最坏情况下会形成一条链，查找退化成 O(n)。

按秩合并的思路是让"矮的树"接在"高的树"下面，从而保持整体树的高度尽量小。这里的"秩"在经典实现中通常指树的高度上界，当两个秩相同的树合并时，新树的秩加一。

public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } count--; }

在岛屿数量这道题上，count的递减非常关键。只有真的发生了合并，集合总数才减少，如果两个节点本来就在同一个集合里，count不能减。

3. "岛屿数量"并查集完整代码：一次 AC 的工程实践

3.1 完整可运行的 Java 代码

下面是可直接提交到 LeetCode 的完整代码，注释几乎可以当作讲解稿来读：

class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; // 第一步：初始化并查集，把所有陆地视为独立节点 UnionFind uf = new UnionFind(grid); // 第二步：遍历每个格子，只向右和向下合并，避免重复操作 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { int index = i * cols + j; // 二维转一维 if (j + 1 < cols && grid[i][j + 1] == '1') { uf.union(index, index + 1); } if (i + 1 < rows && grid[i + 1][j] == '1') { uf.union(index, index + cols); } } } } return uf.getCount(); } // 内部类：并查集 class UnionFind { int[] parent; int[] rank; int count; // 岛的数量 public UnionFind(char[][] grid) { int rows = grid.length; int cols = grid[0].length; parent = new int[rows * cols]; rank = new int[rows * cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { int index = i * cols + j; parent[index] = index; count++; // 每块陆地初始都是一个独立的岛 } else { parent[index] = -1; // 水，标记为无效节点 } } } } public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } // 按秩合并 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } count--; // 只有真正合并，岛屿数才减少 } public int getCount() { return count; } } }

3.2 代码中的几个"别有用心"的设计

第一个是只向右和向下合并。四方向遍历当然也可以，但每个格子都检查上下左右，必然导致大量重复操作。比如格子 (0,0) 检查右边 (0,1) 合并了一次，等遍历到 (0,1) 时又检查左边 (0,0) 再合并一次，虽然 find 会判断出已连接，但白白浪费了两次查找的开销。只检查右和下，既能保证所有相邻陆地都被合并，又消除了冗余。这个优化思路在面试时主动说出来，是很加分的。

第二个是把二维坐标压缩成一维 ID。公式index = i * cols + j是网格类并查集问题的核心技巧。一维索引的好处是parent和rank数组不需要开二维，代码简洁，而且向右合并只需index + 1，向下合并只需index + cols，非常直观。

第三个是用parent[index] = -1标记水域。这样在后续 find 时，如果误把水域传进去，通过 parent 数组的值能很快发现异常。不过严格来说，numIslands 主函数的遍历逻辑只会对grid[i][j] == '1'的格子调用 union，所以 -1 标记更多是防御性编程的意思，能帮你第一时间定位 bug。

3.3 为什么 count 能准确反映岛屿数量

初始化的逻辑是：每一块陆地单独算一个岛屿，水不算。比如一个 3x3 的全陆地图，count 初始化是 9，经过 8 次成功的 union 后，count 变成 1，表示最终只有一个岛。又比如一个全水图，count 始终是 0，因为循环里根本没有陆地可初始化，最后返回 0。

关键点在于：union 里必须count--且只在两个根不同时递减。如果你把count--放在if (rootX == rootY) return;之前，逻辑就错了，合并同一个集合会把岛屿数减成负数。这种细节非常容易在面试高压状态下写错。

4. 手推一遍：4x5 网格是怎么从 9 块陆地变成 3 座岛的

4.1 模拟初始化过程

假设输入是：

1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1

先做初始化。遍历所有格子，把 9 块陆地依次建立对应的parent节点，parent[i]=i，count 为 9。二维坐标与一维索引的对应关系是：第 0 行第 0 列 -> 0，第 0 行第 1 列 -> 1，第 1 行第 0 列 -> 4，第 1 行第 1 列 -> 5，第 2 行第 2 列 -> 10，第 3 行第 3 列 -> 15，第 3 行第 4 列 -> 16。

这个坐标到索引的映射是整道题最容易乱的地方，我的习惯是先在草稿纸上把网格按一维展开写下每个格子对应的索引，再开始手推合并，这样不容易出错。

4.2 逐次合并过程

• 遍历 (0,0)，右边 (0,1) 是陆地，合并 0 和 1，count 变 8；
• 遍历 (0,1)，右边 (0,2) 是水，下边 (1,1) 是陆地，合并 1 和 5，count 变 7；
• 遍历 (0,2)，不是陆地，跳过；
• 遍历 (1,0)，右边 (1,1) 是陆地，合并 4 和 5。此时 find(4)=4，find(5) 会一路找到根 0（因为 5 的父节点已经是 0 了），合并 4 到 0，count 变 6；
• 遍历 (1,1)，右边 (1,2) 是水，下边 (2,1) 是水，无操作；
• 遍历 (2,2)，右边是水，下边的 (3,2) 是水，无操作；
• 遍历 (3,3)，右边 (3,4) 是陆地，合并 15 和 16，count 变 5；
• 遍历 (3,4)，没有右边和下边，无操作。

最终 count 等于 5？这不对，预期应该是 3。等下，我再数一遍陆地块数。这个 4x5 网格里的'1'是：左上角 2x2 四块，中间 (2,2) 一块，右下角 (3,3)(3,4) 两块，共 7 块。初始 count 应该是 7，不是 9。上面我说 9 是笔误。

重新推：初始化 count = 7。第一次合并 0 和 1 后变 6，第二次合并 1 和 5 后变 5，第三次合并 4 和 5 后变 4，第四次合并 15 和 16 后变 3。最终 count = 3，也就是左上角岛、正中间岛、右下角岛，正确。

4.3 路径压缩带来的"蝴蝶效应"

注意上面第三步合并中，find(5)的返回值很关键。在第二次合并时，我们已经把 1 和 5 合并了，而且实现时rank[1]和rank[5]相等，所以parent[5] = 1，同时rank[1]变成 1。到了第三次合并时，find(5)先找到 1，1 的父节点是 0（因为第一次合并时parent[1] = 0），所以 5 的根是 0。路径压缩后，5 的父节点直接从 1 改成 0，以后任何以 5 为入口的 find 只需两步。

如果没有路径压缩，树会越并越高，find 的代价越来越大。路径压缩加按秩合并，两者结合才能保证并查集的操作均摊复杂度接近 O(α(n))，其中 α 是反阿克曼函数，增长极慢，实际可以认为是 O(1)。

5. 边界情况与易错点排查实录

5.1 空输入与单行单列

最容易翻车的不是算法本身，而是输入边界。grid为 null、grid.length == 0、grid[0].length == 0这三种情况都要单独处理，代码里直接返回 0 即可。单行网格如{"10101"}也必须正确处理，此时i + 1 < rows永远为 false，只会走向右合并的逻辑，最终 count 是 3，三块陆地各自成岛，正确。单列网格{{'1'},{'1'},{'0'},{'1'}}同理，只走向下合并，最终 count 是 2。

很多人写这道题时会在grid[0].length上报空指针异常，就是因为忽略了grid.length == 0的情况。LeetCode 的测试用例有时会直接给你一个空的二维数组，稳一点的做法是一开始就做三层判断：

if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) { return 0; }

5.2 第二维长度不一致带来的越界问题

我自己在本地测试时遇到过一个问题：故意构造了一个不规则的二维数组，比如第一行 3 列、第二行 4 列。这类非矩阵输入在 LeetCode 上不会出现，但本地测试要小心。本题假定网格是规整的char[][]，所有行的列数一致，代码里grid[i][j + 1]依赖这个假设。所以写测试用例时一定要用规则矩阵，否则越界异常会让你误以为算法有 bug。

5.3 把水也初始化进并查集

有些初学者会把所有格子都初始化成节点，包括'0'的水域，然后 union 时只操作陆地。这样 parent 数组里水域节点始终是孤立节点，最后数 count 时会把水域也算进去。避免方式就是上面的写法：只有陆地才parent[index] = index和count++，水域设为 -1，不参与统计。

另一种常见的错误写法是在 numIslands 结束后再遍历 parent 数组统计parent[i] == i的节点数量，这种方法也能得到岛屿数，因为水域的 parent 是 -1，不算根节点。但这样做的缺陷是：如果你把水域节点也初始化成parent[i] = i，统计就会出错。所以要么统一用 count 变量，要么统一用根节点统计法，别混用。

6. 面试官追问时，你能答到什么层级

6.1 复杂度分析要讲清楚"为什么是 O(MN·α(MN))"

主函数遍历整个网格是 O(MN)，每次 union 和 find 因为路径压缩和按秩合并，均摊时间复杂度是 O(α(MN))。α 是反阿克曼函数，在人类能遇到的任何输入规模下都不超过 4，所以面试时可以直接说"近似 O(MN)"。

但这里有个微妙的点：初始化 parent 和 rank 数组要遍历 grid 一次，合并又要遍历 grid 一次，所以常数项是 2，但大 O 还是 O(MN)。空间复杂度方面，parent 和 rank 各是 O(MN)，加上原本的 grid 是输入，不纳入额外空间的话，就是 O(MN)。

有个细节值得在面试时主动提：rank 字段可以省吗？可以，但合并时退化风险大。理论上只用路径压缩的并查集，单次 find 的均摊复杂度已经是 O(log n)，实际也够快，但配合按秩合并才能达到理论上的 O(α(n))。对于岛屿数量这种只需要最终统计的场景，省掉 rank 用随机合并，在 LeetCode 的数据量下不会超时，但面试官会怀疑你只背了模板、不理解秩的含义。

6.2 并查集 vs DFS vs BFS 的对比

实际面试时，如果面试官让你用两种方法做，我的建议是先讲 DFS 把题目做出来，再讲并查集方案，最后主动对比：DFS 的搜索天然适合回答"从一个点出发能到达哪些地方"，并查集更像"维护一张连接关系网"。这样既展示基础，又展示抽象能力。

6.3 并查集在同类问题里的弹药库

岛屿数量只是并查集应用的入门，把这道题吃透后，下面这些题基本可以秒杀：

• LeetCode 130"被围绕的区域"：用并查集把所有边界上的'O'连到一个虚拟节点，再遍历内部'O'判断是否和虚拟节点连通；
• LeetCode 990"等式方程的可满足性"：先把所有==的变量合并，再检查!=的变量是否在同一集合；
• LeetCode 684"冗余连接"：在无向图中找一条导致成环的边，边遍历边 union，遇到find相同的两条边就是答案；
• LeetCode 323"无向图中连通分量的数量"：比岛屿数量更直接的并查集应用，N 个节点初始 count 就是 N，每条边合并一次，最后 count 就是答案。

这类问题的共同模式是：先找节点，再找节点之间"相邻"或"关系"的定义，然后套并查集模板。网格类的节点是一维扩展索引，图论类的节点就是 0 到 n-1 的编号，本质完全一样。

7. 写在最后：关于这道题我的真实体会

我至少带过 5 个学弟学妹刷这道题，自己也重新写过多遍，每次都有新感悟。并查集模板本身很固定，难点不在实现，而在于你能不能在读题 30 秒内意识到"这道题是并查集"。我的判断方法很简单：如果题目里出现了"连通""分区""圈子""冗余连接""是否属于同一集合"这些词，优先往并查集想。

另外分享一下我在用通义千问等代码辅助工具排查本地测试用例时的习惯：先把自己的代码和测试数据喂进去，请工具帮忙检查有没有数组越界或逻辑漏洞，但核心算法一定自己先想清楚。工具可以帮你节省 debug 时间，却不能替你做抽象建模。

最后一个小建议：不要只满足于 AC。拿出草稿纸，把一个 4x5 的网格手动模拟一遍合并过程，你才能真切感受到 count 是怎么一步步降下来的。写完并查集版本后，再回头写一遍 DFS 版本，比较两种思维差异。这样花的一个小时，性价比比闷头刷十道新题高得多。