岛屿的最大面积：BFS 和 DFS 模板
# 📃 题目描述
题目链接：
- 剑指 Offer II 105. 岛屿的最大面积 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
- 695. 岛屿的最大面积 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0。
示例 1:
输入: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出: 6
解释: 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
# 🔔 解题思路
应用与图相关的算法解决问题的第1步是找出问题中隐含的图。看到这个题目之后，可能会有人问：输入的是一个矩阵，图在哪里？
以这个矩阵为例：
其实图是节点和边的集合，因此需要找出图的节点和边。这个题目关注的是地图中的岛屿，也就是矩阵中的1。矩阵中的每个值为1的格子都是图中的一个节点。矩阵中的一个格子可能与位于它上、下、左、右的4个格子相邻，两个相邻的值为1的格子之间有一条边相连。例如，可以用下图表示上图的岛屿。
一个图可能包含若干互不连通的子图，但子图内的所有节点相互连通，每个子图对应一个岛屿。
将岛屿转换成图之后，岛屿的面积就变成子图中节点的数目。如果能计算出每个连通子图中节点的数目，就能知道最大的岛屿的面积。
可以逐一扫描矩阵中的每个格子，如果遇到一个值为 1 的格子并且它不在之前已知的岛屿上，那么就到达了一个新的岛屿，于是搜索这个岛屿并计算它的面积。在比较所有岛屿的面积之后就可以知道最大的岛屿的面积。
整个搜索、比较的过程可以用如下所示的代码实现：
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
// 标识矩阵中的每个值为 1 的格子是否已经到达过
boolean[][] visited = new boolean[rows][cols];
int maxArea = 0;
// 逐一扫描矩阵中的每个格子
for (int i = 0; i < rows; i ++) {
for (int j = 0; j < cols; j ++) {
// 如果遇到一个值为 1 的格子并且它不在之前已知的岛屿上，那么就到达了一个新的岛屿，于是搜索这个岛屿并计算它的面积
if (grid[i][j] == 1 && !visited[i][j]) {
int area = getArea(grid, visited, i, j);
maxArea = Math.max(maxArea, area);
}
}
}
return maxArea;
}
}
上述代码最重点的地方就是这个 if 判断：如果遇到一个值为 1 的格子并且它不在之前已知的岛屿上，那么就到达了一个新的岛屿，于是搜索这个岛屿并计算它的面积
其中，具体的搜索 getArea 可以用 BFS 也可以用 DFS
构建图最重要的部分就是找相邻节点！
# BFS
// BFS grid[row, col] 所在岛屿
private int getArea(int[][] grid, boolean[][] visited, int row, int col) {
// 队列中用数组存储每个格子的坐标
Queue<int[]> queue = new LinkedList<>();
// 起始节点入队
queue.offer(new int[]{row, col});
// 记录当前节点是否访问过
visited[row][col] = true;
// 记录 grid[row, col] 所在岛屿的面积
int area = 0;
// 上下左右四个方向
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
// 当前层节点的个数
int size = queue.size();
for (int k = 0; k < size; k ++) {
// 从队列中取出一个节点
int[] pos = queue.poll();
area ++;
// 上下左右四个方向上值为 1 的格子依次入队
for (int[] dir : dirs) {
int i = pos[0] + dir[0]; // 横坐标
int j = pos[1] + dir[1]; // 纵坐标
if ((i >= 0 && i < grid.length) &&
(j >= 0 && j < grid[0].length) &&
grid[i][j] == 1 && !visited[i][j]) {
queue.offer(new int[]{i, j});
visited[i][j] = true;
}
}
}
}
return area;
}
⭐ 和层序遍历代码基本差不多，可以看到，遍历图就三个地方需要注意：
- 队列中只存储值为 1 的节点（陆地）
- 找相邻节点（可以说，知道了如何找相邻的陆地节点，就相当于图已经被构建出来了）
- 记录已经访问过的节点
总结下本题的 BFS 思路：以值为 1 的土地为起点（初始化的时候将值为 1 的节点加入队列中），依次搜索和每层值为 1 的土地的距离（循环处理队列的时候要将值 1 的节点加入队列）
当然了，前面我们也说过，对于层序遍历来说，如果我们不需要依赖每一层遍历的结果的话，其实那个
for (int k = 0; k < size; k ++)循环是可以省略掉的，如下：
// BFS grid[row, col] 所在岛屿
private int getArea(int[][] grid, boolean[][] visited, int row, int col) {
// 队列中用数组存储每个格子的坐标
Queue<int[]> queue = new LinkedList<>();
// 起始节点入队
queue.offer(new int[]{row, col});
// 记录当前节点是否访问过
visited[row][col] = true;
// 记录 grid[row, col] 所在岛屿的面积
int area = 0;
// 上下左右四个方向
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
// 从队列中取出一个节点
int[] pos = queue.poll();
area ++;
// 上下左右四个方向上值为 1 的格子依次入队
for (int[] dir : dirs) {
int i = pos[0] + dir[0]; // 横坐标
int j = pos[1] + dir[1]; // 纵坐标
if ((i >= 0 && i < grid.length) &&
(j >= 0 && j < grid[0].length) &&
grid[i][j] == 1 && !visited[i][j]) {
queue.offer(new int[]{i, j});
visited[i][j] = true;
}
}
}
return area;
}
⭐ 总的来说，BFS 大概分为以下几个步骤
1）起始节点入队，并设为已访问
2）循环处理队列
从队列中弹出一个节点
循环处理该节点的所有邻居节点
- 若邻居节点未访问过，则入队并设为已访问
# DFS
⭐ 事实上，这种连通性的问题，用 DFS 来做比 BFS 的效率更高
# 迭代
其实就是将 BFS 代码中的队列替换成栈，由于栈按照 “后进先出” 的顺序进行压栈、出栈操作，因此图搜索的顺序相应地变成深度优先搜索
// DFS
private int getArea(int[][] grid, boolean[][] visited, int row, int col) {
Stack<int[]> stack = new Stack<>();
// 起始节点入栈
stack.push(new int[]{row, col});
visited[row][col] = true;
int area = 0;
// 上下左右四个方向
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!stack.isEmpty()) {
int size = stack.size();
for (int k = 0; k < size; k ++) {
// 从栈中取出一个节点
int[] pos = stack.pop();
area ++;
// 上下左右四个方向上值为 1 的格子依次入栈
for (int[] dir : dirs) {
int i = pos[0] + dir[0]; // 横坐标
int j = pos[1] + dir[1]; // 纵坐标
if ((i >= 0 && i < grid.length) &&
(j >= 0 && j < grid[0].length) &&
grid[i][j] == 1 && !visited[i][j]) {
stack.push(new int[]{i, j});
visited[i][j] = true;
}
}
}
}
return area;
}
# 递归
当然了，DFS 其实一般都是用递归来写的，比较简洁：
从起始节点出发的岛屿的面积等于起始节点的面积（一个节点的面积为 1）加上与之相邻并且没有访问过的节点能到达的岛屿的面积。求相邻节点能到达的岛屿的面积和初始问题完全一样，可以用递归函数求得。
// DFS
private int getArea(int[][] grid, boolean[][] visited, int row, int col) {
// 访问 gird[row][col] 这块格子
visited[row][col] = true;
// gird[row][col] 所在岛屿的面积，注意这里初始化为 1
int area = 1;
// 上下左右四个方向
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// DFS 上下左右四个方向上值为 1 的格子
// 以 4 个方向探索与 grid[i][j] 相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通岛屿的面积
for (int[] dir : dirs) {
int i = row + dir[0]; // 横坐标
int j = col + dir[1]; // 纵坐标
if ((i >= 0 && i < grid.length) && (j >= 0 && j < grid[0].length) &&
grid[i][j] == 1 && !visited[i][j]) {
area += getArea(grid, visited, i, j);
}
}
return area;
}
总结 DFS 递归模板，分为以下几步：
1）当前节点设置为已访问
2）循环处理当前节点的所有邻居节点
- 若邻居节点未访问过，则 DFS 处理该邻居节点
# 💥 复杂度分析
- 空间复杂度：
- 时间复杂度：
🎁 公众号
各位小伙伴大家好呀，叫我小牛肉就行，目前在读东南大学硕士，上方扫码关注公众号「飞天小牛肉」，与你分享我的成长历程与技术感悟~