算法-深度优先搜索DFS

深度优先搜索（DFS）是一种用于遍历或搜索树、图等数据结构的算法。它的核心思想是尽可能深地探索一个分支，直到无法继续前进，再回溯到上一个分叉点尝试其他路径。以下通过细胞数量问题为你详细讲解DFS的核心逻辑和应用场景：

一、DFS的基本原理

DFS的工作方式类似于走迷宫：

选择一个起点开始探索。
沿着一条路径走到尽头，并标记走过的位置。
遇到死路后回退到上一个分叉点，尝试其他未走过的路径。
重复上述过程，直到所有可能的路径都被探索。

伪代码表示

void dfs(当前位置) {if (当前位置不合法) return;if (当前位置已访问过) return;标记当前位置为已访问;for (所有相邻位置) {dfs(相邻位置); // 递归探索所有方向}
}

常见DFS题型

DFS 数学问题

数学问题可以用 “位数“ 作为突破口。dfs移位，for循环遍历每一位可以填什么值，也就是“几种选择” 选？不选？选哪几种？枚举可选情况。该类问题常需要回溯

典例1：全排列

学习DFS全排列是一个非常经典的例子。

对于n=3的全排列

从1开始遍历不断dfs深搜，一定要从头到尾看代码把所有结果捋一遍，dfs函数返回到哪里，返回之后执行什么逻辑？

package DFS;import java.util.Scanner;//全排列   那很经典了
public class Main04 {static boolean[] visited=new boolean[20];public static void dfs(int x,int []arr,int N) {if(x>N) {//遍历到N+1层了，说明前N位的数都找到了,arr数组已存满//打印一下for(int i=0;i<N;i++) {System.out.print(arr[i]);}System.out.println();return;}for(int i=1;i<=N;i++) {//这遍历到了第i个数字if(!visited[i]) {//第i个数还没用过，那这层就用一下吧。//另外要是用过的话，就直接跳到下一个循环看看i+1呗arr[x-1]=i;visited[i]=true;dfs(x+1, arr,N);//恢复状态arr[x-1]=0;visited[i]=false;//完事了，跳到下一次循环看看i+1什么情况。//要是已经i=N了那就可以返回调用处，到上一层了}}}public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int N=scanner.nextInt();int[] arr=new int[N];dfs(1,arr,N);}
}

典例2：组合

package DFS;import java.util.Scanner;//组合  5个数字选3个   
//那就是三层 枚举每一层可以放那些数字
public class Main05 {static boolean[] visited=new boolean[100];public static void dfs(int x,int N,int[] arr,int start,int R) {//x是当前枚举到了第x层if(x>R) {for(int i=1;i<=R;i++) {System.out.print(arr[i]);	}System.out.println();return;}//要保证前一位的数字大于后一位的，则后一位要从上一位的数字+1开始遍历for(int i=start;i<=N;i++) {visited[i]=true;arr[x]=i;dfs(x+1, N, arr, i+1, R);visited[i]=false;arr[x]=0;}}public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int N=scanner.nextInt();int R=scanner.nextInt();int []arr=new int[20];dfs(1,N,arr,1,R);//起始层数是1}}

要保证前一位的数字大于后一位的，则后一位要从上一位的数字+1开始遍历

要知道每调用一次dfs，位数就要后移一位。X表示当前枚举到了哪一位

后移的一位要经历for循环中每一个数的遍历

DFS应用题

DFS递归调用，进入DFS方法首先要把当前坐标设置为已经访问过，相当于f(n)=f(n-1) ,注意n-1,这是跳到下一层递归的条件，还要注意定义flag，if语句限定已经访问过的数据（点，坐标）不再访问

做题思路

前提条件：地图（图），树
准备工作：定义全局变量（static）visited[][]数组，标记节点访问情况
for循环遍历地图的每一个节点，找到符合题意的节点进行dfs
dfs偏移量递归，一般偏移量不止一种情况，需要用到for循环
回溯（非必须）
注意事项：某点进入dfs后要更新标记情况true。考虑数组越界情况

例一：小朋友崇拜圈

package DFS;import java.util.Arrays;
import java.util.Scanner;//遍历小朋友，dfs崇拜对象，dfs回到最开始的小朋友则为一圈
public class Main02 {static int maxCount = 0;//i第i-1个小朋友，j崇拜对象，arr小朋友崇拜数组public static void dfs(int current, int Q, int[] arr, int count, boolean[] visited) {if (current == Q && count > 0) {// 形成环maxCount = Math.max(maxCount, count);return;}if (visited[current - 1] == true) {// 访问到已经访问过的节点return;}//判断完current基本情况后，标记访问数组visited[current - 1] = true;dfs(arr[current - 1], Q, arr, count + 1, visited);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int[] arr = new int[N];boolean[] visited = new boolean[N];for (int i = 0; i < N; i++) {arr[i] = scanner.nextInt();}// 小朋友初始化好了，arr[i]是第i+1个小朋友崇拜的对象for (int Q = 1; Q <= N; Q++) {dfs(Q, Q, arr, 0, visited);Arrays.fill(visited, false);}System.out.println(maxCount);}}

为什么使用DFS？因为需要遍历每一个小朋友，并且每个小朋友都有相邻节点图结构

根据做题方法，

前提条件：小朋友崇拜圈（图结构），考虑使用DFS遍历所有小朋友节点
准备工作：visited数组，标记节点情况
开始for循环遍历每一个小朋友，每一个小朋友都符合题意（即有相邻节点），因此每个小朋友都要用dfs搜索一遍
dfs偏移量递归，本题偏移量就是下一个小朋友
另外需要考虑是否要回溯？索引越界情况？visited数组是否在正确标记了true？

例二：全球变暖

经典的DFS问题 -->岛屿问题

根据题意找出一个#，他的上下左右都是#,这样形状的至少五个#形成的岛屿不会被侵蚀。题目要求找到含有#但不含有上述五个#形成的岛屿，即会被侵蚀的岛屿。

为什么用DFS？因为要遍历整个地图（图），并且符合题意的节点都有要搜索的相邻节点，搜索相邻节点就需要用DFS

根据做题方法

1.前提条件：海域地图（图结构），考虑使用DFS遍历所有地图上的节点

2.准备工作：visited数组，标记节点情况

3.开始for循环遍历每一个地图节点，只有#是符合DFS的节点（即有符合题意的相邻节点），因此每个#都要用dfs搜索一遍

4.dfs偏移量递归，本题偏移量就是#的四个方向上的节点

5.另外需要考虑是否要回溯？索引越界情况？visited数组是否正确标记了true？

三、回溯适用条件判断（难点）

在深度优先搜索（DFS）中，是否使用回溯取决于问题的状态管理需求。以下是关键区别及示例说明：

需要回溯的情况

当不同递归路径共享同一状态，且需要尝试所有可能性时，必须回溯以恢复状态。

特点

状态共享：多个路径修改同一数据结构（如列表、数组）。
路径探索：需撤销当前选择以尝试其他可能（如排列、组合问题）。

示例

全排列
生成数组的所有排列时，每次选择一个元素后，需记录已选元素。递归返回后需撤销选择，以便尝试其他排列.....代码如上

路径总和II
记录所有满足条件的路径时，需在递归后移除当前节点，防止污染其他路径：

void dfs(TreeNode node, int target, List<Integer> path, List<List<Integer>> res) {if (node == null) return;path.add(node.val);if (node.left == null && node.right == null && target == node.val) {res.add(new ArrayList<>(path));}dfs(node.left, target - node.val, path, res);dfs(node.right, target - node.val, path, res);path.remove(path.size() - 1); // 回溯：移除当前节点
}

无需回溯的情况

当状态独立维护或修改后无需恢复时，不需要回溯。

特点

状态独立：每次递归传递值的副本（如基本类型、不可变对象）。
永久修改：状态修改后无需撤销（如标记已访问的岛屿）。

示例

二叉树的前序遍历
每个节点仅访问一次，路径独立，无需恢复状态：

void dfs(TreeNode node, List<Integer> res) {if (node == null) return;res.add(node.val); // 无需回溯dfs(node.left, res);dfs(node.right, res);
}

岛屿数量
遍历后将陆地标记为水（永久修改），无需恢复：

void dfs(char[][] grid, int i, int j) {if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;grid[i][j] = '0'; // 直接修改，无需回溯dfs(grid, i + 1, j);dfs(grid, i - 1, j);dfs(grid, i, j + 1);dfs(grid, i, j - 1);
}

回溯总结

场景	是否需要回溯	原因	示例
共享状态且需尝试所有路径	是	不同路径共享同一数据结构，需恢复状态	全排列、组合问题
独立状态或永久修改	否	状态通过值传递或修改后无需撤销	二叉树遍历、岛屿数量

核心判断：是否需要撤销当前选择以允许其他路径的正确执行。若多个分支共享可变状态，则必须回溯；反之，若状态独立或修改不可逆，则无需回溯。

以例题形式理解回溯

以P1451 求细胞数量 - 洛谷为例，目标是统计矩阵中连通的非零区域（细胞）的数量。DFS在此处的核心作用是标记并探索整个连通区域。

关键步骤

遍历矩阵：逐个检查每个单元格。
触发DFS的条件：当遇到未被访问过的非零单元格时，启动DFS。
标记连通区域：在DFS中标记所有与该单元格连通的非零单元格为已访问。
计数细胞：每次触发DFS时，计数器加1（表示发现一个新细胞）。

package DFS;import java.util.Scanner;public class Main08 {static int n;static int m;static boolean[][] visited=new boolean [100][100];static int[][] map;static int count=0;static int[] dy= {0,0,1,-1};static int[] dx= {1,-1,0,0};public static void dfs(int y,int x) {if(y<0||y>n-1||x<0||x>m-1) {//索引越界return ;}if(map[y][x]==0) {//这个方向走到0了，不是细胞return;}if(visited[y][x]) {//访问过了return;}visited[y][x]=true;int nextY;int nextX;for(int i=0;i<4;i++) {nextY=y+dy[i];nextX=x+dx[i];dfs(nextY,nextX);}}public static void main(String[] args) {Scanner sc=new Scanner(System.in);n=sc.nextInt();m=sc.nextInt();map=new int[n][m];// 读取地图for (int i = 0; i < n; i++) {String line = sc.next();for (int j = 0; j < m; j++) {map[i][j] = line.charAt(j) - '0';}}for(int i=0;i<n;i++) {for(int j=0;j<m;j++){if(map[i][j]!=0&&!visited[i][j])count++;dfs(i,j);}}System.out.println(count);}}

为什么不需要回溯？

在细胞数量问题（岛屿类问题）中，DFS不需要回溯，因为：

永久标记：一旦标记某个单元格为已访问（visited[i][j] = true），后续遍历会直接跳过它，避免重复计数。
目标单一：只需统计连通区域的数量，而非列举所有可能的路径。DFS的职责是“淹没”整个细胞区域，无需恢复状态。

对比需要回溯的场景

场景	是否需要回溯	原因
细胞数量问题	否	标记是永久的，只需统计数量
全排列问题	是	需要撤销选择以尝试其他排列组合
迷宫路径搜索	是	需要回退以探索不同路径的可能解

四、DFS的两种典型应用

1. 不回溯的场景（标记型DFS）

问题特征：只需遍历或标记所有可达节点。
常见问题：
- 统计连通区域（细胞、岛屿数量）
- 二叉树的前序遍历
- 图的连通性判断

代码特点：

使用visited数组记录已访问节点。
递归后不需要撤销操作。

2. 需要回溯的场景（路径探索型DFS）

问题特征：需要尝试所有可能的路径或组合。
常见问题：
- 全排列、组合总和
- 棋盘问题（如八皇后）
- 子集生成