岛屿数量——DFS/BFS/并查集三种解法完整实现
岛屿数量——DFS/BFS/并查集三种解法完整实现
适读人群：Java 后端工程师、准备算法面试的同学 | 阅读时长：约22分钟 | 难度：Medium
开篇故事
200 题（岛屿数量）是图论里出现频率最高的题，没有之一。凡是我接触过的中大厂面试，几乎有一半会考图的连通性问题，而岛屿数量就是最基础的连通性问题。
DFS 版本大家基本都会写，但 BFS 版本和并查集版本就不一定了。我专门把三种方法都写完整，因为这三种方法在不同场景下各有优势：
DFS 代码最简洁，但递归深度等于岛屿面积，大岛屿容易栈溢出；BFS 用队列避免了深递归，更适合生产代码；并查集在"动态合并"场景下无可替代——比如"在线添加陆地，每次添加后查询岛屿数量"这类问题。
这三种方法代表了解决连通性问题的三条不同路线，每条路线在图论里都有大量变体应用。
一、题目解析
题目：LeetCode 200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水拦截，并且每座岛屿只能由水平方向和/或垂直方向上相邻的陆地连接形成。
示例：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3约束： m == grid.length，n == grid[i].length，1 <= m, n <= 300
二、解法一：DFS（深度优先搜索）
思路
遍历网格，遇到 '1' 就把它以及所有与它连通的陆地标记为已访问（用 DFS 向四个方向扩展，把 '1' 改成 '0'）。每次发起 DFS 就是发现了一个新岛屿，计数加 1。
完整代码
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int r, int c) {
// 边界检查和已访问检查
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') {
return;
}
grid[r][c] = '0'; // 标记为已访问（把陆地"淹没"）
// 向四个方向扩展
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
}复杂度分析
- 时间复杂度：O(m*n)。每个格子最多被访问两次（外层遍历一次，DFS 标记一次）。
- 空间复杂度：O(m*n)。递归栈深度最坏情况（整个网格都是陆地）为 m*n。
注意： 当 mn = 300300 = 90000 时，递归深度可达 90000，Java 默认线程栈大小约 512KB-1MB，每帧几十字节，可能导致栈溢出。生产代码建议用迭代 BFS。
三、解法二：BFS（广度优先搜索）
思路
和 DFS 相同的整体框架，但把向外扩展的方式从递归 DFS 改成 BFS 队列。避免了深递归的栈溢出风险。
完整代码
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
grid[i][j] = '0'; // 立刻标记，避免重复入队
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] dir : dirs) {
int nr = cell[0] + dir[0];
int nc = cell[1] + dir[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
queue.offer(new int[]{nr, nc});
}
}
}
}
}
}
return count;
}
}复杂度分析
- 时间复杂度：O(m*n)。每个格子进出队列最多一次。
- 空间复杂度：O(min(m,n))。队列最大存储一层的格子数，在蔓延状岛屿中最坏是 min(m,n)。
BFS 的空间开销通常比 DFS 小（不需要深度等于面积的栈），是生产代码的首选。
四、解法三：最优解法——并查集
思路
并查集用于动态维护连通分量。
初始化时，每个 '1' 格子是一个独立的集合。然后遍历每个 '1'，检查它的右侧和下侧（避免重复检查）是否也是 '1'，如果是，就合并这两个格子所在的集合（Union）。
最终，并查集中集合的数量就是岛屿数量。
Mermaid 图——并查集合并过程
完整代码（含路径压缩和按秩合并）
class Solution {
class UnionFind {
int[] parent;
int[] rank;
int count; // 连通分量数量（岛屿数量）
UnionFind(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
parent = new int[rows * cols];
rank = new int[rows * cols];
count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
parent[i * cols + j] = i * cols + j;
count++;
}
// '0' 的格子 parent 不初始化，find 时不会被查询
}
}
}
// 路径压缩
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 按秩合并
void union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return;
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank[px]++;
}
count--; // 合并后岛屿数量减 1
}
int getCount() { return count; }
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length, cols = grid[0].length;
UnionFind uf = new UnionFind(grid);
int[][] dirs = {{0, 1}, {1, 0}}; // 只检查右侧和下侧，避免重复合并
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
for (int[] dir : dirs) {
int ni = i + dir[0], nj = j + dir[1];
if (ni < rows && nj < cols && grid[ni][nj] == '1') {
uf.union(i * cols + j, ni * cols + nj);
}
}
}
}
}
return uf.getCount();
}
}复杂度分析
- 时间复杂度：O(mn * α(mn))。α 是反阿克曼函数，实际上接近 O(1)，总体近似 O(m*n)。
- 空间复杂度：O(m*n)。parent 和 rank 数组。
三种方法对比
| 方法 | 时间 | 空间 | 优点 |
|---|---|---|---|
| DFS | O(mn) | O(mn) 递归栈 | 代码最简洁 |
| BFS | O(mn) | O(min(m,n)) | 无栈溢出风险，生产首选 |
| 并查集 | O(mn*α) | O(mn) | 支持动态添加陆地查询 |
提交结果（并查集版）：时间击败约 85% 用户，空间击败约 60% 用户。
五、举一反三
同类题目
LeetCode 695. 岛屿的最大面积 不计岛屿数量，而是找最大的一个岛屿的面积，DFS/BFS 时记录面积即可。
LeetCode 463. 岛屿的周长 不需要 DFS，直接遍历每个陆地格子，统计它的邻居中水格子的数量（每个水邻居贡献 1 条边）。
LeetCode 1905. 统计子岛屿 较复杂变体，grid1 中的陆地格子必须在 grid2 中也是陆地，判断 grid2 的岛屿是否是 grid1 岛屿的子集。
LeetCode 305. 岛屿数量 II 动态添加陆地，每次添加后查询岛屿数量，经典并查集应用。
六、踩坑实录
坑一：DFS 访问标记时机——先标记还是后标记
BFS 版本里，格子入队时就要立刻标记为 '0'，而不是出队时才标记。如果出队时才标记，同一个格子可能被多次入队（多个方向同时发现它），浪费空间，严重时导致 MLE。
坑二：并查集初始化时 '0' 格子不初始化
parent 数组的大小是 rows * cols，但只有 '1' 格子需要初始化 parent。'0' 格子的 parent 值是 0（int 数组默认值），但因为 '0' 格子不会参与 find 和 union 操作，不会影响结果。
坑三：并查集的 union 函数减计数时机
每次成功合并（两个格子的根节点不同，才真正合并）时，count 减 1。如果已经是同一连通分量就不合并，count 也不减。
坑四：修改了原始 grid 数组
DFS 和 BFS 版本都通过把 '1' 改成 '0' 来标记已访问。这修改了输入数组，可能在某些场景下不被允许。如果不能修改输入，可以用额外的 boolean[][] visited 数组记录访问状态，代价是多 O(m*n) 空间。
坑五：只检查两个方向的合法性
并查集版本里只检查右侧（0,1）和下侧（1,0），但 DFS/BFS 版本里需要检查四个方向。并查集只检查两个方向是因为：左侧和上侧已经在之前的遍历中处理过了（当时以左/上的格子为中心，检查了它的右/下），不需要重复检查。
七、总结
200 题是图的连通性问题里最基础的一道，但三种解法各有侧重，值得深入理解：
DFS 对应的是"沿着图的深度方向探索"的递归思维；BFS 对应的是"按层扩展"的队列思维，更稳健；并查集对应的是"维护连通关系"的数据结构思维，在动态场景下无可替代。
这三种工具在图论题库里会反复用到。建议按 DFS -> BFS -> 并查集的顺序掌握，每种都要能闭眼写出，这样遇到各种变体题才能灵活应对。