深度优先搜索
一提到DFS，很多人脑子里可能冒出来的是“递归”、“栈”、“回溯”这些词。没错，但这些都是实现它的工具。那DFS的本质是什么？
在我看来，DFS的本质就是 “一条路走到黑，不撞南墙不回头” 的莽夫精神。
想象你在走一个迷宫，怎么走？最符合直觉的策略就是，随便选一个路口，一直走下去。如果遇到死胡同了，怎么办？退回到上一个路口，换个方向再试试。如果这个路口的所有方向都试过了，还是死胡同，那就再退回到上上个路口……直到找到出口，或者所有路都试完了，发现根本没出口。
这就是DFS的核心思想：深入探索，走不通再退回，换路再探。
光说不练假把式。我们来看一个最经典的题目：岛屿数量。
题目： 给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和竖直方向上相邻的陆地连接形成。
// 例子
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
// 这个网格里有 3 个岛屿。
解法一：最直观的解法 —— 递归
拿到这个题，我第一反应就是，遍历整个网格。当我遇到一个 '1'（陆地）时，我就找到了一个新岛屿的“一部分”。
那怎么确定整个岛屿的范围呢？
很简单，从这个点出发，向它的上下左右四个方向去探索。如果邻居也是 '1'，那它就和我是同一块岛屿。然后，再从这个邻居出发，继续向它的邻居的邻居探索......
这个过程听起来是不是很熟悉？这就是一个典型的递归过程。
process(i, j) 函数的含义就是：请把 (i, j) 位置以及所有与它相连的陆地都给我“淹掉”（比如变成'2'），这样下次就不会重复计算了。
思路：
写一个主函数，用两层 for 循环遍历整个
grid。循环中，如果
grid[i][j] == '1'，说明我们发现了一个新岛屿。此时，岛屿数量islands++。为了不重复计算，我们需要把这个新发现的岛屿的所有陆地都标记一下，表示“已访问”。怎么标记？就从
(i, j)这个点开始，进行深度优先搜索，把所有相连的 '1' 都改成一个特殊字符，比如 '2' 或者 '0'。这个DFS过程，就交给一个递归函数
infect(grid, i, j)来做。
infect(grid, i, j) 的逻辑：
Base Case (递归出口):
如果
(i, j)越界了 (i < 0, i >= rows, j < 0, j >= cols)，直接返回。如果
grid[i][j]不是 '1'（说明是水，或者是已经访问过的陆地），也直接返回。
递归过程:
先把当前的
grid[i][j]标记为已访问，比如grid[i][j] = '2'。然后，莽夫精神来了：一条路走到黑。
往上走：
infect(grid, i - 1, j)往下走：
infect(grid, i + 1, j)往左走：
infect(grid, i, j - 1)往右走：
infect(grid, i, j + 1)
这个递归过程会像病毒一样，从一个点开始，感染所有与它相连的 '1'，把它们都变成 '2'。当 infect 过程结束后，整个岛屿就被“淹没”了。主循环继续扫描，直到找到下一个 '1'。
代码实现:
public class Solution1_RecursiveDFS {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
islands++;
infect(grid, i, j);
}
}
}
return islands;
}
// 递归函数：把(i,j)以及相邻的陆地都变成'2'
private void infect(char[][] grid, int i, int j) {
int rows = grid.length;
int cols = grid[0].length;
// Base Case: 越界或不是陆地，就返回
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1') {
return;
}
// 将当前陆地标记为已访问
grid[i][j] = '2';
// 向四个方向递归探索
infect(grid, i - 1, j); // 上
infect(grid, i + 1, j); // 下
infect(grid, i, j - 1); // 左
infect(grid, i, j + 1); // 右
}
}
递归解法非常直观，代码也简洁。但它有个问题，如果岛屿的形状特别“深”，比如说一条长长的蛇形，递归深度可能会非常大，有导致栈溢出（StackOverflowError）的风险。
那有没有办法不使用系统栈，自己来控制这个过程呢？
解法二：自己动手，丰衣足食 —— 迭代与栈
系统递归的本质是利用函数调用栈来保存现场。我们完全可以自己模拟这个过程。用什么来模拟？当然是 栈（Stack）。
思路：
主函数的逻辑和解法一完全一样：遍历网格，遇到 '1' 就
islands++，然后开始“淹没”这个岛屿。“淹没”的过程，我们不用递归，而是用一个栈来辅助。
创建一个栈，把当前发现的陆地坐标
(i, j)压入栈中。同时，为了防止重复入栈，先把
grid[i][j]标记为已访问 ('2')。进入一个
while循环，只要栈不为空，就说明这个岛屿还有部分没探索完。在循环中：
弹出一个坐标
(cur_i, cur_j)。查看它的四个邻居
(next_i, next_j)。如果邻居是合法的（不越界）并且是 '1'（未访问的陆地），就把这个邻居的坐标压入栈中，并立刻标记为 '2'。
当
while循环结束时，栈空了，说明与(i, j)相连的所有陆地都被访问并标记过了。整个岛屿“淹没”完毕。
这个过程和递归的本质是一样的。递归是隐式地用系统栈，而我们现在是显式地用一个我们自己创建的 Stack 数据结构来做同样的事情。
代码实现:
import java.util.Stack;
public class Solution2_IterativeDFS {
// 辅助类，用来存坐标
private static class Position {
int x, y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
islands++;
// 使用栈来“淹没”岛屿
Stack<Position> stack = new Stack<>();
stack.push(new Position(i, j));
grid[i][j] = '2'; // 标记为已访问
while (!stack.isEmpty()) {
Position current = stack.pop();
int curI = current.x;
int curJ = current.y;
// 探索四个方向
// 上
if (curI - 1 >= 0 && grid[curI - 1][curJ] == '1') {
stack.push(new Position(curI - 1, curJ));
grid[curI - 1][curJ] = '2';
}
// 下
if (curI + 1 < rows && grid[curI + 1][curJ] == '1') {
stack.push(new Position(curI + 1, curJ));
grid[curI + 1][curJ] = '2';
}
// 左
if (curJ - 1 >= 0 && grid[curI][curJ - 1] == '1') {
stack.push(new Position(curI, curJ - 1));
grid[curI][curJ - 1] = '2';
}
// 右
if (curJ + 1 < cols && grid[curI][curJ + 1] == '1') {
stack.push(new Position(curI, curJ + 1));
grid[curI][curJ + 1] = '2';
}
}
}
}
}
return islands;
}
}
这种迭代的写法避免了栈溢出的风险，在处理极端测试用例时更稳健。虽然代码看起来比递归版本长一点，但思路同样清晰。
那么，还有没有别的搞法？DFS的玩法当然不止这些。
解法三：不改原数组的“干净”解法 —— 引入 visited 数组
前面两种解法都直接修改了输入的 grid 数组。在很多面试或实际工程中，修改输入参数可能是不被允许的，被认为是一种“不纯”的函数行为。
那我们可以在不修改 grid 的前提下完成任务吗？
当然可以。我们只需要一个和 grid 等大的辅助空间，专门用来记录哪些位置被访问过。通常我们会用一个 boolean[][] visited 数组。
这个思路可以应用在递归和迭代两种实现上，我们以递归为例进行改造。
思路：
在主函数中，额外创建一个
boolean[][] visited数组，所有元素初始为false。主循环遍历
grid，判断条件变为：grid[i][j] == '1' && !visited[i][j]。当这个条件满足时，我们才发现了一个新的、未被访问过的岛屿。islands++后，调用infect(grid, i, j, visited)。infect函数的逻辑几乎不变，只是把 “修改grid[i][j]为 '2'” 这个操作，换成 “修改visited[i][j]为true”。Base Case: 增加了
visited[i][j] == true的判断。递归过程: 将
visited数组作为参数传递下去。
代码实现:
public class Solution3_VisitedArrayDFS {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 发现一个新岛屿的未访问部分
if (grid[i][j] == '1' && !visited[i][j]) {
islands++;
infect(grid, i, j, visited);
}
}
}
return islands;
}
private void infect(char[][] grid, int i, int j, boolean[][] visited) {
int rows = grid.length;
int cols = grid[0].length;
// Base Case: 越界、是水域、或已访问过
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0' || visited[i][j]) {
return;
}
// 标记为已访问
visited[i][j] = true;
// 向四个方向递归探索
infect(grid, i - 1, j, visited);
infect(grid, i + 1, j, visited);
infect(grid, i, j - 1, visited);
infect(grid, i, j + 1, visited);
}
}
这种方法用空间换来了对原数组的保护，代码逻辑同样清晰。在需要保持输入数据不变的场景下，这是首选方案。
总结一下
今天我们用三种方式搞定了“岛屿数量”这个问题，但这三种方式的核心都是深度优先搜索（DFS）：
递归DFS：最直观，代码最简洁，但有栈溢出风险。
迭代DFS（手动栈）：模拟递归过程，避免了栈溢出，性能更稳定。
使用
visited数组的DFS：不修改原数组，是更规范、更通用的写法。