深度优先搜索（DFS，Depth-First Search）是一种用于遍历或搜索树或图的算法。DFS 从起始节点开始，尽可能深入每一条分支，直到无法继续为止。然后回溯到上一个节点，继续未访问的其他分支，直到所有节点都被访问过。

通过一个 岛屿计数 问题来讲解 DFS 的应用。问题要求我们计算一个二维矩阵中所有连通的“岛屿”数量，岛屿由 1 组成，水域由 0 组成。每个岛屿由若干相邻的 1 连接构成，可以上下左右相邻。

问题描述

给定一个 n × m 的二维矩阵，1 表示陆地，0 表示水域。我们需要找到其中所有岛屿的数量。一个岛屿是由相连的 1 组成的区域，相邻的 1 可以通过上下左右方向连接。

深度优先搜索（DFS）算法步骤

1. 遍历矩阵：从每个未访问的 1 开始，执行 DFS，标记所有与该 1 相连的陆地为已访问，表示找到了一个岛屿。
2. 回溯标记：DFS 的递归过程会探索当前岛屿所有相连的 1，直到没有更多陆地可访问。
3. 岛屿计数：每次开始新的 DFS 递归时，岛屿数量加 1。

代码解析

以下是基于 DFS 算法解决岛屿计数问题的 Java 代码模板：

import java.io.*; 
import java.util.*;public class Main {public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));public static StreamTokenizer in = new StreamTokenizer(br);public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static int[][] dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };public static void main(String[] args) throws Exception {int n = nextInt();  // 读取行数int m = nextInt();  // 读取列数int[][] arr = new int[n][m];// 读取二维矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = nextInt();}}// 初始化访问标记数组boolean[][] visited = new boolean[n][m];int ans = 0;  // 岛屿计数器// 遍历整个矩阵，执行 DFS 搜索for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果当前点是陆地并且没有被访问过if (!visited[i][j] && arr[i][j] == 1) {ans++;  // 找到一个岛屿，计数器加1visited[i][j] = true;  // 标记为已访问dfs(visited, i, j, arr);  // 从该点进行 DFS 搜索}}}out.println(ans);  // 输出岛屿数量out.flush();out.close();br.close();}// 深度优先搜索函数，标记所有相连的陆地public static void dfs(boolean[][] visited, int x, int y, int[][] arr) {// 四个方向的移动（右，下，上，左）for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 检查新位置是否越界if (nextX < 0 || nextY < 0 || nextX >= arr.length || nextY >= arr[0].length) {continue;  // 越界则跳过}// 如果当前格子是陆地并且未访问过if (!visited[nextX][nextY] && arr[nextX][nextY] == 1) {visited[nextX][nextY] = true;  // 标记为已访问dfs(visited, nextX, nextY, arr);  // 递归继续搜索}}}// 读取整数输入public static int nextInt() throws Exception {in.nextToken();return (int) in.nval;}

关键点解析

1. 矩阵输入：

   • 使用 StreamTokenizer 读取输入，这对于大规模输入数据非常高效。可以将其替换为更常见的 Scanner，根据实际需求选择输入方式。

2. DFS 函数：

   • dfs 函数的作用是从当前节点 (x, y) 开始，递归访问所有与其相连的陆地 1，并将其标记为已访问。我们用 visited 数组来记录哪些节点已经访问过。
   • dir 数组定义了四个方向（右、下、上、左），通过 nextX 和 nextY 来计算相邻的节点坐标。

3. 岛屿计数：

   • 每当我们在 arr[i][j] == 1 且该位置尚未被访问时，我们认为发现了一个新的岛屿，岛屿计数器 ans 加 1。然后通过 DFS 遍历这个岛屿，并标记所有相连的陆地。

4. 边界检查：

   • 在 dfs 函数中，边界检查非常重要，因为我们要确保递归不会访问超出矩阵范围的节点。检查是否越界的代码如下：

if (nextX < 0 || nextY < 0 || nextX >= arr.length || nextY >= arr[0].length)continue;

时间复杂度分析

• 时间复杂度：O(n * m)，其中 n 是矩阵的行数，m 是列数。每个节点最多被访问一次，因此总体复杂度是矩阵的大小。
• 空间复杂度：O(n * m)，主要用于存储 visited 数组和递归调用栈。