当前位置：首页 > news >正文

图论——岛屿数量

news 2026/4/17 10:12:29

题目：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

岛屿数量是经典的 深度优先搜索（DFS）和广度优先搜索（BFS） 算法题，核心思路：
1.遍历二维网格的每一个格子；
2.遇到陆地'1'时，说明找到一座新岛屿，岛屿数量+1；
3.立即把这座岛屿所有相连的陆地全部标记为水'0'（避免重复统计）；
4.最终统计的总数就是岛屿数量。

深度优先搜索（DFS）递归实现
public class NumberOfIslands {

public int numIslands(char[][] grid) {// 边界判断：网格为空直接返回0if (grid == null || grid.length == 0) {return 0;}int row = grid.length;    // 网格行数int col = grid[0].length; // 网格列数int count = 0;            // 岛屿数量// 遍历每一个格子for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {// 找到未被访问的陆地if (grid[i][j] == '1') {count++; // 岛屿+1// DFS：把当前岛屿所有陆地标记为水dfs(grid, i, j);}}}return count;
}// DFS递归函数：标记所有相连的陆地为水
private void dfs(char[][] grid, int i, int j) {int row = grid.length;int col = grid[0].length;// 递归终止条件：越界 或 当前是水，直接返回if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == '0') {return;}// 标记当前陆地为水（已访问）grid[i][j] = '0';// 递归搜索 上下左右 四个方向dfs(grid, i - 1, j); // 上dfs(grid, i + 1, j); // 下dfs(grid, i, j - 1); // 左dfs(grid, i, j + 1); // 右
}// 测试示例
public static void main(String[] args) {NumberOfIslands solution = new NumberOfIslands();char[][] grid = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};System.out.println("岛屿数量：" + solution.numIslands(grid)); // 输出 3
}

}

代码解释
1.主函数：双重循环遍历网格所有格子，遇到陆地就计数 + 1，并启动 DFS；
2.DFS 函数：

先判断是否越界 / 是水，是则终止递归；
把当前陆地改为水（标记已访问）；
递归遍历上下左右四个相邻格子。

关键点解释：

1. 递归遍历只是把与这片岛屿相连的陆地标记为水，而不是把整个网格全淹，因为dfs的if条件一遇到水grid[i][j]=='0'就退出递归，所以，DFS只淹当前连通的那一块

2. grid==null||grid.length ==0的两个判断完全不一样，缺一不可

grid==null
防：变量根本没指向任何数组
char[][] grid = null;
意思是：这里空空如也，连数组的影子都没有。
如果你不判断，直接去写 grid.length，直接报空指针错误，程序挂掉！
2.grid.length == 0
防：有数组，但数组是空的（一行都没有）
意思是：有一个空箱子，但箱子里什么都没有。
这时候 grid 不是 null，但 grid.length 是 0。