在计算机科学中，图（Graph） 和 树（Tree） 是表达复杂关系的核心数据结构。当需要遍历或搜索这些结构时，深度优先搜索（Depth-First Search, DFS） 是最基本、最直观的算法之一。它模拟了“一条路走到黑，碰壁再回头”的探索策略，广泛应用于路径查找、连通性检测、拓扑排序、迷宫求解等场景。
1. 深度优先搜索的核心思想
DFS 的核心是“深入优先”的遍历策略：
- 从起点出发：选择一个起始节点（或顶点）。
- 沿着路径深入：访问该节点，然后选择其一个未被访问的邻居，递归地深入探索。
- 回溯（Backtrack）：当到达一个“死胡同”（所有邻居都已被访问）时，回退到上一个节点，继续探索其其他未被访问的邻居。
- 重复：直到所有从起点可达的节点都被访问。
DFS 的过程天然地与递归（Recursion） 或栈（Stack） 结构相匹配。递归调用栈隐式地记录了回溯路径。
2. 基础实现：图的 DFS 遍历
假设我们有一个无向图，使用邻接表（Adjacency List） 表示。
3. 经典应用：岛屿数量（LeetCode 200）
问题描述： 给定一个由 '1'（陆地）和 '0'（水）组成的二维网格 grid。岛屿是由 '1' 在水平或垂直方向上连接形成的。计算网格中岛屿的数量。
解题思路：
- 遍历整个网格。
- 当遇到一个
'1'（陆地）时，说明发现了一个新的岛屿。 - 使用 DFS 从该点开始，将与之相连的所有
'1'（整个岛屿）都“淹没”（标记为 '0' 或使用 visited 数组），防止重复计数。 - 每成功启动一次 DFS，岛屿数量加一。
/**
* 计算二维网格中的岛屿数量
*
* @param grid 二维字符数组，'1' 表示陆地，'0' 表示水
* @return 岛屿的数量
*/
public static int numIslands(char[][] grid) {
// 边界检查
if (grid == null || grid.length == 0 || grid[0].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++) {
// 如果当前单元格是陆地 ('1')
if (grid[i][j] == '1') {
count++; // 发现新岛屿，计数加一
// 使用 DFS 将整个岛屿“淹没”（标记为 '0'）
dfs(grid, i, j, rows, cols);
}
}
}
return count;
}
/**
* DFS 辅助函数：从 (row, col) 开始，淹没相连的陆地
*/
private static void dfs(char[][] grid, int row, int col, int rows, int cols) {
// 边界检查和终止条件
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
return; // 越界或遇到水，停止
}
// 将当前陆地标记为水（'0'），表示已访问
grid[row][col] = '0';
// 递归探索四个方向：上、下、左、右
dfs(grid, row - 1, col, rows, cols); // 上
dfs(grid, row + 1, col, rows, cols); // 下
dfs(grid, row, col - 1, rows, cols); // 左
dfs(grid, row, col + 1, rows, cols); // 右
}
// 测试方法
public static void main(String[] args) {
char[][] grid = {
{'1','1','0','0','0'},
{'1','1','0','0','0'},
{'0','0','1','0','0'},
{'0','0','0','1','1'}
};
int result = numIslands(grid);
System.out.println("岛屿数量: " + result); // 输出: 3
}4. 算法复杂度分析
- 时间复杂度：O(M × N)
M 是网格的行数，N 是列数。- 在最坏情况下，每个单元格都会被访问一次（主循环访问一次，DFS 可能再访问一次）。但由于
dfs 函数会将访问过的 '1' 改为 '0'，所以每个 '1' 最多只会被 dfs 访问一次。总体时间复杂度为 O(M × N)。
- 空间复杂度：O(M × N)
- 主要消耗在递归调用栈上。
- 在最坏情况下（整个网格都是
'1'，形成一个巨大的岛屿），递归深度可能达到 M × N（例如，DFS 路径呈蛇形遍历整个网格），此时空间复杂度为 O(M × N)。 - 平均情况下，空间复杂度取决于岛屿的大小和形状。
'%3e%3c/path%3e%3c/g%3e%3c/g%3e%3c/svg%3e)
'%3e%3c/path%3e%3c/g%3e%3c/g%3e%3c/svg%3e)
在计算机科学中，图（Graph） 和 树（Tree） 是表达复杂关系的核心数据结构。当需要遍历或搜索这些结构时，深度优先搜索（Depth-First Search, DFS） 是最基本、最直观的算法之一。它模拟了“一条路走到黑，碰壁再回头”的探索策略，广泛应用于路径查找、连通性检测、拓扑排序、迷宫求解等场景。
1. 深度优先搜索的核心思想
DFS 的核心是“深入优先”的遍历策略：
DFS 的过程天然地与递归（Recursion） 或栈（Stack） 结构相匹配。递归调用栈隐式地记录了回溯路径。
2. 基础实现：图的 DFS 遍历
假设我们有一个无向图，使用邻接表（Adjacency List） 表示。
import java.util.*; public class DFS { // 图的邻接表表示 private Map<Integer, List<Integer>> graph; // 记录节点是否被访问过 private Set<Integer> visited; public DFS() { this.graph = new HashMap<>(); this.visited = new HashSet<>(); } /** * 添加一条边 (u, v) */ public void addEdge(int u, int v) { graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v); graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u); // 无向图 } /** * 从节点 start 开始进行深度优先搜索 */ public void dfs(int start) { // 标记当前节点为已访问 visited.add(start); System.out.print(start + " "); // 访问操作（例如打印） // 获取当前节点的所有邻居 List<Integer> neighbors = graph.getOrDefault(start, new ArrayList<>()); for (int neighbor : neighbors) { // 如果邻居未被访问，则递归深入 if (!visited.contains(neighbor)) { dfs(neighbor); } } // 函数返回时，自动回溯到上一个节点 } // 重置访问状态，以便进行下一次遍历 public void reset() { visited.clear(); } // 测试方法 public static void main(String[] args) { DFS dfs = new DFS(); // 构建图: 1-2-3, 4-5 dfs.addEdge(1, 2); dfs.addEdge(2, 3); dfs.addEdge(4, 5); System.out.print("从节点 1 开始 DFS: "); dfs.dfs(1); // 输出: 1 2 3 System.out.println(); dfs.reset(); // 重置 System.out.print("从节点 4 开始 DFS: "); dfs.dfs(4); // 输出: 4 5 System.out.println(); } }3. 经典应用：岛屿数量（LeetCode 200）
问题描述： 给定一个由
'1'（陆地）和'0'（水）组成的二维网格grid。岛屿是由'1'在水平或垂直方向上连接形成的。计算网格中岛屿的数量。解题思路：
'1'（陆地）时，说明发现了一个新的岛屿。'1'（整个岛屿）都“淹没”（标记为'0'或使用 visited 数组），防止重复计数。/** * 计算二维网格中的岛屿数量 * * @param grid 二维字符数组，'1' 表示陆地，'0' 表示水 * @return 岛屿的数量 */ public static int numIslands(char[][] grid) { // 边界检查 if (grid == null || grid.length == 0 || grid[0].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++) { // 如果当前单元格是陆地 ('1') if (grid[i][j] == '1') { count++; // 发现新岛屿，计数加一 // 使用 DFS 将整个岛屿“淹没”（标记为 '0'） dfs(grid, i, j, rows, cols); } } } return count; } /** * DFS 辅助函数：从 (row, col) 开始，淹没相连的陆地 */ private static void dfs(char[][] grid, int row, int col, int rows, int cols) { // 边界检查和终止条件 if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') { return; // 越界或遇到水，停止 } // 将当前陆地标记为水（'0'），表示已访问 grid[row][col] = '0'; // 递归探索四个方向：上、下、左、右 dfs(grid, row - 1, col, rows, cols); // 上 dfs(grid, row + 1, col, rows, cols); // 下 dfs(grid, row, col - 1, rows, cols); // 左 dfs(grid, row, col + 1, rows, cols); // 右 } // 测试方法 public static void main(String[] args) { char[][] grid = { {'1','1','0','0','0'}, {'1','1','0','0','0'}, {'0','0','1','0','0'}, {'0','0','0','1','1'} }; int result = numIslands(grid); System.out.println("岛屿数量: " + result); // 输出: 3 }4. 算法复杂度分析
M是网格的行数，N是列数。dfs函数会将访问过的'1'改为'0'，所以每个'1'最多只会被dfs访问一次。总体时间复杂度为 O(M × N)。'1'，形成一个巨大的岛屿），递归深度可能达到M × N（例如，DFS 路径呈蛇形遍历整个网格），此时空间复杂度为 O(M × N)。