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

深度优先搜索(DFS)框架精讲：一网打尽岛屿系列算法题

news 2026/5/22 11:08:28

1. 项目概述：从一道题到一类题的思维跃迁

在算法面试和日常刷题中，我们常常会遇到一类以网格（Grid）为背景的问题，尤其是“岛屿”系列问题。这类问题看似千变万化，从基础的岛屿数量统计，到复杂的岛屿面积、周长计算，再到更高级的封闭岛屿、子岛屿判断，常常让初学者感到无从下手，陷入“一道题一个解法”的困境。实际上，只要你掌握了深度优先搜索（DFS）在这类网格问题上的核心框架与变通逻辑，就能实现“一法通，万法通”，真正做到秒杀整个系列。

“DFS算法秒杀五道岛屿系列问题”这个标题，精准地指向了算法学习中的一个高阶目标：模式识别与框架抽象。它解决的不仅仅是几道具体的LeetCode题目（如200. 岛屿数量、463. 岛屿的周长、695. 岛屿的最大面积、1254. 统计封闭岛屿的数目、1905. 统计子岛屿），更是提供了一套应对所有二维网格遍历问题的通用心法和可复用的代码骨架。其核心价值在于，将看似独立的点状知识，连接成一张网状的、可迁移的解题体系。

对于正在准备技术面试的开发者，或是希望提升算法思维能力的编程爱好者而言，深入理解这个“DFS框架”的价值远超做对五道题本身。它能让你在面对任何新的网格问题时，都能快速定位问题本质，自信地写出清晰、高效的解决方案，从而在面试或竞赛中脱颖而出。接下来，我将以一个从业多年的视角，为你彻底拆解这套框架的每一个细节，分享那些只有踩过坑才能获得的实操心得。

2. 核心框架设计：网格DFS的“万能钥匙”

在深入具体问题之前，我们必须先铸造那把“万能钥匙”——网格DFS的通用框架。这个框架的威力，在于它将复杂的二维空间搜索，抽象为几个简单、固定的组成部分。

2.1 网格的建模与遍历基础

首先，我们要统一对网格的认知。在代码中，网格通常用一个二维字符数组char[][] grid或二维整数数组int[][] grid表示。grid[i][j]代表第i行、第j列的单元格。值为‘1‘或1通常代表陆地（需要处理的部分），值为‘0‘或0代表水域。

遍历网格最直接的方式是双层循环：

for (int i = 0; i < m; i++) { // m 为行数 for (int j = 0; j < n; j++) { // n 为列数 // 对每个单元格 grid[i][j] 进行处理 } }

为什么是双层循环？因为我们必须访问到网格中的每一个位置，这是进行任何全局统计或搜索的前提。任何试图绕过逐个单元格检查的“捷径”在理论上都是不成立的。

2.2 DFS函数的标准化设计

这是整个框架的灵魂。一个标准的、用于处理单个岛屿（或连通分量）的DFS函数签名和核心逻辑如下：

// 方向数组：代表上、右、下、左四个方向的坐标偏移量 int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 核心DFS函数 void dfs(char[][] grid, int i, int j) { // 1. 边界条件判断（递归终止条件）：超出网格范围 if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) { return; } // 2. 业务逻辑判断（递归终止条件）：当前单元格不是陆地，无需处理 if (grid[i][j] != ‘1‘) { return; } // 3. 处理当前单元格（本题中就是将其标记为已访问） grid[i][j] = ‘0‘; // 或 ‘2‘， 目的是避免重复访问 // 4. 递归遍历四个方向上的相邻单元格 for (int[] d : dirs) { int nextI = i + d[0]; int nextJ = j + d[1]; dfs(grid, nextI, nextJ); } }

这个设计为什么是“标准”的？

方向数组dirs：它将四个方向的移动向量化，避免了写四行相似的递归调用代码，使逻辑更清晰，且易于扩展到八方向（如“生命游戏”问题）。
终止条件前置：在递归调用自身之前，先判断下一步是否合法。这比在递归开头判断更符合逻辑，也避免了不必要的函数栈开销。
原地标记已访问：这是最关键的技巧。我们通过修改原网格的值（如将‘1‘改为‘0‘或‘2‘）来替代一个额外的visited[][]布尔数组。这样做的好处是：
- 节省空间：无需 O(m*n) 的额外空间。
- 逻辑直观：被淹没的“陆地”（‘0‘）自然不会再被计入。
- 注意：如果题目不允许修改原数组（极少见），则必须使用visited数组。

实操心得一：关于“沉岛”策略将访问过的陆地标记为水域（‘0‘），这个操作形象地称为“沉岛”。它不仅仅是标记，更是一种“消除”逻辑，确保主循环中的双层for循环，每个岛屿只会被触发一次DFS。这是整个框架能正确统计数量的基石。务必理解，dfs函数一旦从某个陆地单元格启动，就会“吞噬”掉整个连通的岛屿。

2.3 主循环与DFS的协同逻辑

主循环负责“扫描”和“触发”，DFS负责“扩散”和“处理”。它们的协作模式是固定的：

public int solveProblem(char[][] grid) { if (grid == null || grid.length == 0) return 0; int m = grid.length, n = grid[0].length; int result = 0; // 根据具体问题，可能是数量、最大面积等 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == ‘1‘) { // 发现一块“新大陆” // 在这里，可以调用dfs处理整个岛屿 dfs(grid, i, j); // 在dfs调用后，根据问题需求更新结果 result++; // 例如：岛屿数量+1 } } } return result; }

协同的精髓：主循环中的if (grid[i][j] == ‘1‘)是触发DFS的唯一入口。因为DFS会“沉没”整个岛屿，所以当主循环后续扫描到这个岛屿的其他部分时，它们已经变成了‘0‘，不会再触发新的DFS。这样就保证了每个岛屿只被计数一次。

3. 框架的变体与应用：解决五类经典问题

掌握了标准框架，我们就可以像搭积木一样，通过微调DFS函数和主循环的逻辑，来解决岛屿系列的各种变体问题。下面我们逐一拆解。

3.1 问题一：岛屿数量（LeetCode 200）

这是最基础的原型。问题定义：给你一个由‘1‘（陆地）和‘0‘（水）组成的二维网格，计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

解法分析：直接应用上述标准框架即可。主循环中，每遇到一个‘1‘，就启动一次DFS淹没整个岛屿，并将计数器加1。DFS函数完全采用标准形式。

代码实现要点：

public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == ‘1‘) { dfs(grid, i, j); count++; // 触发一次DFS，就找到一个岛屿 } } } return count; } // dfs函数与2.2节中的标准实现完全一致

为什么这么简单？因为问题只关心连通分量的个数，不关心分量内部的任何属性。标准DFS的“淹没”行为恰好完美地完成了“标记一个完整连通分量”的任务。

3.2 问题二：岛屿的最大面积（LeetCode 695）

问题升级：在统计岛屿数量的基础上，你需要找出最大的岛屿面积（即‘1‘的个数）。

框架调整思路： DFS函数不再仅仅是一个“淹没”过程，它还需要成为一个“测量”过程。我们需要让DFS函数返回一个值：从当前单元格(i, j)出发，能遍历到的岛屿面积。

DFS函数改造：

int dfsArea(char[][] grid, int i, int j) { // 终止条件不变 if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != ‘1‘) { return 0; // 不是有效陆地，贡献面积为0 } // 处理当前单元格 grid[i][j] = ‘0‘; int area = 1; // 当前单元格自身贡献1面积 // 递归收集四个方向的面积 for (int[] d : dirs) { area += dfsArea(grid, i + d[0], j + d[1]); } return area; // 返回以(i,j)为起点的岛屿总面积 }

主循环协同：

public int maxAreaOfIsland(int[][] grid) { int maxArea = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { int currentArea = dfsArea(grid, i, j); // 获取当前岛屿面积 maxArea = Math.max(maxArea, currentArea); // 更新最大面积 } } } return maxArea; }

核心变化：DFS函数有了返回值。它从“过程”变成了“函数”。这个小小的改变，使得DFS不仅能修改全局状态（沉岛），还能向上返回信息，极大地扩展了其能力边界。

实操心得二：DFS的返回值设计当DFS需要汇总子问题的结果时（如面积、节点数、路径和），让其返回一个值是最清晰的设计。这本质上是后序遍历的思想：先处理子节点，再结合自身节点得到结果，最后返回给父节点。在网格DFS中，“父节点”就是主循环中的调用者。记住这个模式，它可以解决大量“统计连通分量属性”的问题。

3.3 问题三：岛屿的周长（LeetCode 463）

问题变形：网格中只有一个岛屿（或者你需要计算每个岛屿的周长然后求和），计算这个岛屿的周长。

难点分析：周长不是面积的简单叠加。一条边是周长，当且仅当它是岛屿与水域的边界，或者是岛屿与网格边界的边界。

框架调整思路：我们依然可以用DFS遍历岛屿。关键在于，如何在遍历每个陆地单元格时，计算出它对总周长的贡献。

一个陆地单元格有4条边。
对于每条边，如果它的“外侧”是网格外或者水域，那么这条边就是周长的一部分。
如果它的“外侧”是另一个陆地单元格，那么这条边是内部边，不计入周长。

DFS函数改造（返回值为void，通过参数或全局变量累加周长）：

public int islandPerimeter(int[][] grid) { for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { // 题目保证只有一个岛屿，所以遇到第一个陆地就开始计算并返回即可 return dfsPerimeter(grid, i, j); } } } return 0; } private int dfsPerimeter(int[][] grid, int i, int j) { // 边界条件1：到达网格边界，贡献一条边 if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) { return 1; } // 边界条件2：到达水域，贡献一条边 if (grid[i][j] == 0) { return 1; } // 边界条件3：到达已访问的陆地，不贡献边 if (grid[i][j] == 2) { return 0; } // 标记已访问 grid[i][j] = 2; int peri = 0; // 递归计算四个方向的贡献 for (int[] d : dirs) { peri += dfsPerimeter(grid, i + d[0], j + d[1]); } return peri; }

另一种更易理解的迭代思路：实际上，周长问题可以不用DFS，用一次遍历更直观。遍历每个陆地单元格，检查其四个方向，如果方向上是水域或边界，周长就加1。

public int islandPerimeterSimple(int[][] grid) { int perimeter = 0; int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { for (int[] d : dirs) { int x = i + d[0], y = j + d[1]; // 如果相邻点是边界或者水域，则这条边是周长 if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) { perimeter++; } } } } } return perimeter; }

选择建议：对于明确的单岛屿周长计算，迭代法更简单直接。但DFS解法仍然有意义，它展示了如何用同一套DFS框架处理边界贡献计算的问题，并且能处理多个岛屿的情况（将每个岛屿的周长累加）。

3.4 问题四：统计封闭岛屿的数目（LeetCode 1254）

问题再次升级：现在，我们只关心“封闭岛屿”。封闭岛屿的定义是：一个完全被水域（‘0‘）包围的岛屿。岛屿的任意一个‘1‘如果在网格的边界上，那么这个岛屿就不是封闭的。

框架调整的核心挑战：标准框架会淹没所有岛屿。但我们需要区分：哪些岛屿是接触到边界的（非封闭），哪些是没有接触到的（封闭）。关键在于，接触到边界的岛屿不能算入最终结果。

解题策略——两遍DFS：

第一遍DFS（预处理）：从所有边界上的陆地单元格出发，执行DFS，淹没所有与边界相连的岛屿。这些岛屿就是“非封闭岛屿”。
第二遍DFS（正式计数）：经过第一遍处理后，网格中剩下的陆地，一定位于网格内部，并且被水域包围。此时，再使用标准的“岛屿数量”算法进行计数，得到的就是封闭岛屿的数量。

代码实现：

public int closedIsland(int[][] grid) { int m = grid.length, n = grid[0].length; // 第一遍：淹没所有边界相连的陆地（非封闭岛屿） // 遍历第一行和最后一行 for (int j = 0; j < n; j++) { if (grid[0][j] == 0) dfs(grid, 0, j); // 注意，本题中陆地是0，水域是1，与之前相反 if (grid[m-1][j] == 0) dfs(grid, m-1, j); } // 遍历第一列和最后一列（注意角点已处理过，可从第二行开始） for (int i = 1; i < m-1; i++) { if (grid[i][0] == 0) dfs(grid, i, 0); if (grid[i][n-1] == 0) dfs(grid, i, n-1); } // 第二遍：统计剩余的岛屿（封闭岛屿） int count = 0; for (int i = 1; i < m-1; i++) { // 只需遍历内部区域 for (int j = 1; j < n-1; j++) { if (grid[i][j] == 0) { dfs(grid, i, j); count++; } } } return count; } // 这里的dfs函数是标准的淹没函数，将0变为其他值（如2）

为什么是两遍？这是一个经典的“预处理”思想。第一遍DFS的目的是排除干扰项。它利用了非封闭岛屿必然连接边界这一特性，提前将它们从问题空间中移除。这样，剩余的问题就退化成了我们熟悉的“在内部区域找连通分量”的基础问题。这种“先处理特殊情况，再处理一般情况”的思路，在算法中非常常见。

实操心得三：逆向思维与预处理封闭岛屿问题教会我们，有时直接求解目标（封闭岛屿）很困难，但求解其反面（非封闭岛屿）却很容易。通过一次高效的预处理（淹没边界岛屿），我们简化了原始问题。在遇到复杂条件约束时，不妨思考：能否先处理掉那些不满足约束的情况，让剩下的部分符合一个已知的、简单的模型？

3.5 问题五：统计子岛屿（LeetCode 1905）

这是岛屿系列中较难的一个变体。给你两个m x n的二进制矩阵grid1和grid2，grid2中的岛屿（连通分量）被认为是grid1中的子岛屿，当且仅当grid2中该岛屿的每一个单元格，在grid1中的对应位置都是陆地。

问题本质：判断grid2中的每一个岛屿，其所有单元格是否都被grid1中的陆地所“覆盖”。

框架调整思路：我们依然需要遍历grid2中的所有岛屿。但对于每个岛屿，在DFS遍历的过程中，我们需要增加一个判断逻辑：检查grid2中的每个陆地单元格(i, j)，在grid1中对应位置是否是陆地（grid1[i][j] == 1）。如果整个岛屿的所有单元格都满足这个条件，它才是子岛屿。

DFS函数改造（需要返回值表示当前岛屿是否为子岛屿）：

// 遍历grid2，判断每个岛屿是否被grid1完全包含 public int countSubIslands(int[][] grid1, int[][] grid2) { int count = 0; for (int i = 0; i < grid2.length; i++) { for (int j = 0; j < grid2[0].length; j++) { if (grid2[i][j] == 1) { // 如果dfs返回true，说明这个岛屿是子岛屿 if (dfsCheck(grid1, grid2, i, j)) { count++; } } } } return count; } // DFS函数：淹没grid2中的一座岛屿，并返回该岛屿是否是子岛屿 private boolean dfsCheck(int[][] grid1, int[][] grid2, int i, int j) { // 终止条件：超出grid2边界或不是陆地 if (i < 0 || i >= grid2.length || j < 0 || j >= grid2[0].length || grid2[i][j] != 1) { return true; // 注意：越界或非陆地，不影响“是子岛屿”的判断，返回true } // 关键判断：如果grid2是陆地，但grid1对应位置是水，则整个岛屿肯定不是子岛屿 // 我们可以立即返回false吗？不行，我们还需要继续淹没这个岛屿，避免主循环重复访问。 // 所以，我们先标记，但记录一个“失效”状态。 // 更优雅的做法：让DFS返回boolean，但遇到不符合条件时，继续执行淹没，但最终返回false。 // 标记grid2已访问 grid2[i][j] = 0; // 当前单元格是否满足子岛屿条件 boolean isSub = (grid1[i][j] == 1); // 递归检查四个方向 boolean b1 = dfsCheck(grid1, grid2, i+1, j); boolean b2 = dfsCheck(grid1, grid2, i-1, j); boolean b3 = dfsCheck(grid1, grid2, i, j+1); boolean b4 = dfsCheck(grid1, grid2, i, j-1); // 只有当前单元格和所有子区域都满足条件，整个岛屿才是子岛屿 return isSub && b1 && b2 && b3 && b4; }

逻辑精讲：

dfsCheck函数有两个任务：淹没grid2中的岛屿，并判断该岛屿是否为子岛屿。
判断逻辑是与（AND）关系：当前单元格是子岛屿的一部分(grid1[i][j]==1)，并且其上下左右四个方向连接的区域也构成子岛屿。
如果某个单元格grid2[i][j]==1但grid1[i][j]==0，那么isSub为false，会导致整个递归链的返回值最终为false。
即使中途发现不是子岛屿，我们仍然需要继续执行DFS（将grid2[i][j]置0），这是为了完成“淹没”任务，确保主循环不会重复遍历这个岛屿的其他部分。这就是为什么不能一遇到grid1[i][j]==0就立即返回false并停止递归的原因。

另一种更清晰的写法（使用全局或外部变量标记）：

private boolean isValid; // 标记当前遍历的岛屿是否有效（是子岛屿） private void dfsMark(int[][] grid1, int[][] grid2, int i, int j) { // 终止条件 if (i < 0 || i >= grid2.length || j < 0 || j >= grid2[0].length || grid2[i][j] != 1) { return; } // 检查关键条件 if (grid1[i][j] != 1) { isValid = false; // 发现不满足条件的单元格，标记整个岛屿无效 // 不return，继续淹没 } grid2[i][j] = 0; // 淹没 // 四个方向递归 dfsMark(grid1, grid2, i+1, j); dfsMark(grid1, grid2, i-1, j); dfsMark(grid1, grid2, i, j+1); dfsMark(grid1, grid2, i, j-1); } public int countSubIslands2(int[][] grid1, int[][] grid2) { int count = 0; for (int i = 0; i < grid2.length; i++) { for (int j = 0; j < grid2[0].length; j++) { if (grid2[i][j] == 1) { isValid = true; // 假设这个岛屿是子岛屿 dfsMark(grid1, grid2, i, j); if (isValid) { // 遍历完后检查标记 count++; } } } } return count; }

这种写法将“判断”和“淹没”分离，逻辑上更容易理解：dfsMark只负责淹没和设置有效性标志，主循环根据标志计数。

4. 深度优化与边界情况处理

掌握了基本框架和变体，我们还需要关注一些深层次的优化技巧和边界情况，这能让你在实战中更加游刃有余。

4.1 DFS的递归深度与栈溢出风险

网格DFS本质是递归，当岛屿面积非常大时（例如整个网格都是陆地），递归深度可能达到m*n，对于较大的网格（如500*500），递归深度25万层，极有可能导致栈溢出（StackOverflowError）。

解决方案：迭代DFS（使用栈）将递归调用改为显式地使用栈（Stack）数据结构来模拟递归过程。

void dfsIterative(char[][] grid, int i, int j) { Stack<int[]> stack = new Stack<>(); stack.push(new int[]{i, j}); grid[i][j] = ‘0‘; // 入栈即标记 int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; while (!stack.isEmpty()) { int[] cell = stack.pop(); int x = cell[0], y = cell[1]; // 注意：这里不需要再判断grid[x][y]，因为入栈时已标记 for (int[] d : dirs) { int newX = x + d[0]; int newY = y + d[1]; if (newX >=0 && newX < grid.length && newY >=0 && newY < grid[0].length && grid[newX][newY] == ‘1‘) { stack.push(new int[]{newX, newY}); grid[newX][newY] = ‘0‘; // 关键：入栈前标记，避免重复入栈 } } } }

为什么入栈前标记？这是为了避免同一个单元格被多次压入栈中。想象一下，A单元格将邻居B压入栈，在后续处理中，B单元格又可能将A（已标记但尚未出栈）再次压入栈，造成冗余和混乱。提前标记可以保证每个单元格只被处理一次。

BFS（广度优先搜索）作为替代对于单纯的连通分量标记，BFS（使用队列）是迭代DFS的一个很好的替代，逻辑类似，只是将栈（Stack）换成了队列（Queue），遵循先进先出的顺序。BFS同样能避免递归深度问题。

实操心得四：递归与迭代的选择在面试或竞赛中，如果网格规模明确不大（比如题目约束 m, n <= 50），递归DFS代码简洁，是首选。如果规模较大，或者你对栈溢出有顾虑，应主动提及迭代DFS/BFS作为优化方案，这能体现你的工程思维和对极端情况的考虑。在实际编码中，我通常先写递归版本，因为它更符合思维直觉，在通过所有测试后，如果性能分析发现是递归深度问题，再重构为迭代版本。

4.2 方向数组的扩展与“八连通”问题

我们一直使用的是四方向（上、右、下、左）的dirs数组。但有些问题定义“相邻”包括对角线，即八方向。例如，某些“矿藏”或“细胞”问题中，对角接触也算连通。

八方向数组：

int[][] dirs8 = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };

使用方式：只需将标准DFS函数中遍历dirs的循环，改为遍历dirs8即可。框架的其他部分完全不变。

注意：“岛屿”问题通常默认为四连通（水平垂直），而“细胞”或“好友关系”问题可能定义为八连通。务必仔细审题。

4.3 复杂状态标记与多源DFS

有时，网格中的单元格可能有多种状态，不止“陆地”和“水域”两种。例如，在“被围绕的区域”（LeetCode 130）问题中，有‘O‘（未处理）、‘X‘（墙）、以及一个中间状态（如‘#‘，表示与边界相连的‘O‘）。

处理方式：我们的标记系统需要扩展。可以使用与原值不同的字符进行标记，也可以使用额外的二维数组。核心原则是：在DFS过程中，能清晰区分“已访问未处理”、“已访问且已归类”等不同状态。

多源DFS：在“腐烂的橘子”（LeetCode 994）或“墙与门”（LeetCode 286）这类问题中，DFS/BFS的起点不是单一的，而是网格中所有符合某个条件的点（如所有腐烂的橘子、所有的门）。这时，我们可以在初始化时，将所有起点先放入队列或栈中，然后再开始搜索。这依然是标准框架的变体，只是初始化步骤不同。

5. 从框架到思维：举一反三的秘诀

通过以上五个问题的详细拆解，我们可以看到，网格DFS的核心框架是稳定不变的。变化的只是DFS函数内部的处理逻辑（如是否返回值、返回什么值）以及主循环前后的预处理和后处理。

举一反三的思维流程：

识别问题类型：看到二维网格、连通分量、遍历、统计等关键词，立刻想到DFS/BFS框架。
定义单元格状态与操作：明确题目中网格值的含义（如0/1， ‘X‘/‘O‘），并确定DFS中“已访问”的标记方式（通常是修改原值）。
设计DFS函数的行为：
- 是否需要返回值？如果需要汇总信息（面积、周长、是否满足条件），则设计返回值。
- 递归过程中需要记录什么？是否需要全局变量或传入参数来记录路径、状态等。
- 终止条件是什么？除了边界和非法状态，是否还有业务相关的终止条件？
设计主循环的逻辑：
- 是否需要预处理？如封闭岛屿问题，先处理边界。
- 触发DFS的条件是什么？通常是遇到“未访问的起始点”。
- 如何利用DFS的结果？是直接计数，还是比较大小，还是累加？
考虑优化与边界：
- 网格很大吗？是否需要迭代DFS/BFS？
- 方向是四连通还是八连通？
- 输入为空网格怎么办？