DFS(深度优先搜索)

深圳信奥中心-禹云龙

2026-10-31 01:15:56

发布于：广东

14阅读

0回复

0点赞

阅读导航

第 1 节：DFS 入门与决策树。
第 2—7 节：六道例题 D1—D6。
第 8—9 节：方法总结、复杂度与二进制枚举对照。

1. DFS 入门

先看一个简单问题：从三个活动中选择若干个，每个活动只有“参加”和“不参加”两种决定。三个活动可以写三层循环，但如果活动数量由输入决定，代码就无法事先固定循环层数。

可以换一种组织方法：第 $1$ 层决定活动 $1$ ，第 $2$ 层决定活动 $2$ ，依次向下。每层使用相同的规则，决定完当前活动后，再处理剩余活动。这就是递归很适合表达的结构。

深度优先搜索（DFS）采用这样的探索顺序： 先沿着当前选择继续向下，直到形成完整方案或无法继续，再返回上一层尝试其他选择。

搜索树通常不需要真正建出来。递归调用的先后关系，就在隐式地遍历这棵树。

1.1 递归的调用与返回

假设某层执行：

dfs(u+1);
cout<<u<<" ";

调用下一层时，本层会暂停。下一层返回后，本层从 cout 继续执行，而不是从函数开头重新执行。

每次调用拥有自己的参数和局部变量。例如下一层的 $u$ 与上一层的 $u$ 是不同的变量。全局数组则由所有层共享，修改后不会因为函数返回而自动恢复。

1.2 决策树

把“每次作出一个选择”的过程画出来，就得到一棵决策树。开始时还没有作出任何选择，处于根节点；作出一次选择，就沿着一条分支到达下一节点。

图中的部分	在搜索中的含义
根节点	开始搜索时的初始状态
节点	某一段决策过程之后，当前已经确定的信息
边或分支	一次具体选择，以及选择造成的状态变化
层	决策推进的进度，常对应已经处理的对象或已经进行的步骤
完成的叶节点	已经无法继续或不必继续作决定；按题目条件判断能否形成答案
从根到叶的路径	一串完整的决策过程

例如，每个活动都有“参加”和“不参加”两个选择，每个决策节点就可以分出两条边。排列问题中，一层可能有多个尚未使用的编号可选，因此决策树不一定只有两个分支。

节点表示的是某段决策过程到达这里后的状态。不同路径下的两个节点，后续问题可能完全相同；此时图上仍先把它们画成两个节点，后面学习记忆化时再讨论能否合并。

1.3 DFS 与决策树遍历

DFS 会先选择一条分支，沿着它继续向下；到达结束条件后返回上层，再尝试尚未访问的分支。

学习时可以先画决策树，再写递归函数：

当前节点需要记录的信息，对应函数参数与必要的共享数组。
当前节点向外的分支，对应循环或几次递归调用。
完成的叶节点，对应递归的结束条件与答案处理。
从子节点返回父节点，对应函数返回；若共享数据受本次选择影响，还要恢复现场。

决策树是帮助分析的图，不要求程序真的创建一棵树。下一道例题就用两个活动画出完整的决策树。

2. 例题 D1：子集枚举

题目

有 $n$ 个活动，编号为 $1$ 到 $n$ 。每个活动可以参加，也可以不参加。输出所有参加方案，方案内编号递增。

按活动编号依次决定，每层先搜索“参加”，再搜索“不参加”。空方案输出 EMPTY。

范围： $1\le n\le 15$ 。

$n=2$ 时，应输出：

1 2
1
2
EMPTY

2.1 状态与搜索分支

定义 $\mathrm{dfs}(u,\mathrm{cnt})$ ：

前 $u-1$ 个活动已经决定完，名单中已有 $\mathrm{cnt}$ 个活动，现在决定第 $u$ 个。

名单存放在 $\mathrm{path}[1\ldots \mathrm{cnt}]$ 。

当前层有两个分支：

参加 $u$ ：把 $u$ 放入名单，然后处理 $u+1$ 。
不参加 $u$ ：名单有效长度不变，然后处理 $u+1$ 。

当 $u=n+1$ ，说明所有活动都已决定，可以输出。

结束条件不能写成 $\mathrm{cnt}=n$ 。 方案可能只参加一个活动，也可能什么都不参加。

2.2 子集枚举的决策树

$n=2$ 时，一层决定一个活动。下图中的每条边是一种选择，最下面四个叶节点对应四个完整方案。

根节点对应 $\mathrm{dfs}(1,0)$ ；处理完第 $1$ 个活动的节点对应 $u=2$ ；叶节点对应 $u=3$ ，即所有活动都已决定。

按“先参加、后不参加”执行 DFS，叶节点的到达顺序是：名单 $1$ 、 $2$ → 名单 $1$ → 名单 $2$ → 空名单。这正是题目要求的输出顺序。

以第一个分支为例：执行 $\mathrm{dfs}(3,2)$ 输出“1 2”后，返回 $\mathrm{dfs}(2,1)$ ，再执行它的“不参加 $2$ ”分支。回到父节点，是为了继续尝试另一种选择，不是重新从根开始。

2.3 核心代码

const int N=20;
int n,path[N];
void dfs(int u,int cnt){
	if(u==n+1){
		if(cnt==0)cout<<"EMPTY";
		for(int i=1;i<=cnt;i++){
			if(i>1)cout<<" ";
			cout<<path[i];
		}
		cout<<"\n";
		return;
	}
	path[cnt+1]=u;
	dfs(u+1,cnt+1);
	dfs(u+1,cnt);
}

调用方式： 读入 $n$ 后执行 $\mathrm{dfs}(1,0)$ 。

2.4 方案数组的使用

只有 $\mathrm{path}[1\ldots \mathrm{cnt}]$ 会被读取。参加下一活动时，对应位置会被覆盖；有效长度之外的旧值不会参与输出。

$\mathrm{cnt}$ 按值传递。第一分支里的 $\mathrm{cnt}+1$ 不会修改当前层的 $\mathrm{cnt}$ ，因此第二分支仍然使用原来的有效长度。

这不是“搜索不用恢复”，而是本例通过有效长度和覆盖写入，避免了额外清空操作。

2.5 搜索的完整性与去重

任一名单都对应唯一的“参加/不参加”决定串；每个决定串也只对应一个名单。每层两个分支覆盖了该活动的所有选择，因此完整搜索不重不漏。

想一想①： 如果改为先“不参加”后“参加”，会不会漏解？输出顺序会怎样变化？

3. 例题 D2：子集求和

题目

有 $n$ 个可选活动，第 $i$ 个需要 $a[i]$ 分钟，每个最多参加一次。求总用时恰好为 $K$ 的方案数。

不同编号视为不同活动，即使用时相同也不合并。空方案计入。

范围： $1\le n\le 22$ ， $1\le a[i]\le 10^{6}$ ， $0\le K\le 2.2\times 10^{7}$ 。

例如 $a=[1,2,3,4]$ 、 $K=5$ ，有两种方案：编号 $(1,4)$ 、 $(2,3)$ 。

3.1 状态设计

定义 $\mathrm{dfs}(u,\mathrm{sum})$ 返回：当前已用时为 $\mathrm{sum}$ ，接下来只考虑 $u$ 到 $n$ 号活动，能形成多少个合法方案。

如果只记录 $u$ ，不同分支来到这里时，距离目标还差的时间不同，后续可行选择也不同，不能混为一谈。

3.2 可行性剪枝

由于所有 $a[i]>0$ ：

$\mathrm{sum}>K$ ：以后无法把总用时减小。
$\mathrm{sum}=K$ ：其余活动只能全部不参加，恰好贡献 $1$ 种完成方式。
$\mathrm{sum}+\text{剩余总用时}<K$ ：全部参加也不够。

设 $\mathrm{suf}[u]=a[u]+\ldots +a[n]$ ，第三条就能快速判断。

3.3 核心代码

const int N=25;
int n;
long long K,a[N],suf[N];
long long dfs(int u,long long sum){
	if(sum==K)return 1;
	if(u==n+1||sum>K||sum+suf[u]<K)return 0;
	return dfs(u****um+a[u])+dfs(u****um);
}
long long countWays(){
	suf[n+1]=0;
	for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];
	return dfs(1,0);
}

调用方式： 读入 $n$ 、 $K$ 、 $a$ 后，countWays() 的返回值是答案。

这里 $\mathrm{sum}=K$ 后直接返回只在所有用时严格为正的条件下成立。若允许 $0$ ，后续零用时活动仍可选，直接返回会漏计；若允许负数， $\mathrm{sum}>K$ 时也可能通过后续选择降回 $K$ 。

4. 例题 D3：组合枚举

题目

从编号为 $1$ 到 $n$ 的学生中选出 $m$ 位代表，输出所有不同组合。每个组合按编号递增，组合之间按字典序输出。

范围： $1\le n\le 20$ ， $0\le m\le n$ ； $m=0$ 时输出 EMPTY。

例如 $n=4$ 、 $m=2$ ：

4.1 组合的含义与去重

选择 $1$ 、 $3$ ，与选择 $3$ 、 $1$ ，在代表名单中是同一个方案。因此可以强制编号递增，让同一个集合只保留一种排列方式。

定义 $\mathrm{dfs}(\mathrm{start},\mathrm{cnt})$ ：已选 $\mathrm{cnt}$ 人，下一人只能从 $\mathrm{start}$ 到 $n$ 中选。

若本次选 $i$ ，下一次从 $i+1$ 开始。

4.2 核心代码

const int N=25;
int n,m,path[N];
void dfs(int start,int cnt){
	if(cnt==m){
		if(m==0)cout<<"EMPTY";
		for(int i=1;i<=m;i++){
			if(i>1)cout<<" ";
			cout<<path[i];
		}
		cout<<"\n";
		return;
	}
	if(n-start+1<m-cnt)return;
	for(int i=start;i<=n;i++){
		path[cnt+1]=i;
		dfs(i+1,cnt+1);
	}
}

调用方式： 读入 $n$ 、 $m$ 后执行 $\mathrm{dfs}(1,0)$ 。

剩余可选人数为 $n-\mathrm{start}+1$ ，还需要 $m-\mathrm{cnt}$ 人。人数不够时直接返回，是有明确依据的可行性剪枝。

想一想②： 若递归写成 $\mathrm{dfs}(i,\mathrm{cnt}+1)$ ，还满足“每人最多选一次”吗？

5. 例题 D4：全排列枚举

题目

将编号 $1$ 到 $n$ 的学生排成一队，输出所有排队顺序，按字典序输出。

范围： $1\le n\le 9$ 。

$n=3$ 时共有六种： $123$ 、 $132$ 、 $213$ 、 $231$ 、 $312$ 、 $321$ 。

5.1 排列与组合的区别

代表名单只关心选中哪些人；排队还关心他们出现的顺序。

现在一层决定一个位置，每层都要从全部尚未使用的编号中选择。用 $\mathrm{vis}[i]$ 表示：编号 $i$ 是否已经出现在当前队伍前缀中。

5.2 核心代码

const int N=15;
int n,path[N];
bool vis[N];
void dfs(int u){
	if(u==n+1){
		for(int i=1;i<=n;i++){
			if(i>1)cout<<" ";
			cout<<path[i];
		}
		cout<<"\n";
		return;
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		path[u]=i;
		vis[i]=true;
		dfs(u+1);
		vis[i]=false;
	}
}

调用方式： $\mathrm{vis}$ 初始为全 $\mathrm{false}$ ，执行 $\mathrm{dfs}(1)$ 。

5.3 回溯与恢复现场

标记为 $\mathrm{true}$ ，是因为当前分支使用了这个人；当前分支结束后，另一个分支仍有权使用他，因此要恢复为 $\mathrm{false}$ 。

本层固定一种选择，进入下一层；返回后撤销这种选择造成的共享影响，再尝试另一种选择。这样，兄弟分支互不干扰。

对照决策树看，恢复现场就是把共享数据恢复到父节点原来的状态。下一个子分支应从同一个父节点出发，不能带着上一个子分支的占用标记继续搜索。

想一想③： 若 $n=3$ 且忘写 $\mathrm{vis}[i]=\mathrm{false}$ ，为什么通常只能输出第一种排列？

6. 例题 D5：迷宫路径搜索

题目

$n$ 行 $m$ 列网格中，. 可走，# 是障碍。从左上角到右下角，每次上下左右移动一格。同一条路线不能重复经过一个格子，求路线数。

范围： $1\le n,m\le 5$ ，可走格子不超过 $18$ 。起终点可能为障碍。

例如 $2\times 2$ 全部可走，答案为 $2$ ：先右再下，或先下再右。

6.1 位置与访问标记

除当前位置外，已经经过哪些格子也会影响下一步能不能走。因此 $\mathrm{vis}$ 记录的是当前路线使用过的格子，而不是整次运行中曾经到达过的格子。

当尝试另一条路线时，一些格子应该重新允许访问。

6.2 核心代码

const int N=10;
int n,m;
char a[N][N];
bool vis[N][N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
long long ans;
void dfs(int x,int y){
	if(x==n&&y==m){
		ans++;
		return;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(a[nx][ny]=='#'||vis[nx][ny])continue;
		vis[nx][ny]=true;
		dfs(nx,ny);
		vis[nx][ny]=false;
	}
}
long long countPaths(){
	ans=0;
	memset(vis,0,sizeof(vis));
	if(a[1][1]=='#'||a[n][m]=='#')return 0;
	vis[1][1]=true;
	dfs(1,1);
	return ans;
}

调用方式： 网格已读入 $a[1\ldots n][1\ldots m]$ ，答案为 countPaths()。

起点必须先标记，否则下一步可能又走回起点。若 $1\times 1$ 网格可走，不移动也是一条合法路线，答案为 $1$ 。

6.3 路径搜索与连通块遍历

若题目只问“从起点能到达多少个不同格子”，每个格子只需处理一次。此时 $\mathrm{vis}$ 的意思变成了“此格子已经统计过”，返回后通常不恢复。

问题	$\mathrm{vis}$ 表示什么	返回时通常恢复吗
排列枚举	当前队伍中已使用的编号	恢复
简单路径计数	当前路线中已经过的格子	恢复
连通块统计	已经归入当前连通块的格子	不恢复

决定是否恢复的，是状态含义，不是函数名。

7. 例题 D6：DFS 求最小值

题目

有 $n$ 个项目，第 $i$ 个贡献 $a[i]$ 点积分，每个最多选择一次。要求总积分至少达到 $K$ ，求最少需要选择多少个项目；无解返回 $-1$ 。

范围： $1\le n\le 22$ ， $1\le a[i]\le 10^{9}$ ， $0\le K\le 2.2\times 10^{10}$ 。

例如 $a=[2,3,7,8]$ 、 $K=10$ ，最少选 $2$ 个项目。

7.1 可行性剪枝与最优性剪枝

定义 $\mathrm{dfs}(u,\mathrm{sum},\mathrm{cnt})$ ：已经选择 $\mathrm{cnt}$ 个项目、得到 $\mathrm{sum}$ 积分，正准备决定第 $u$ 个。

$\mathrm{sum}\ge K$ ：已达标，更新最少数量，继续增加项目不会让数量更少。
$\mathrm{sum}+\mathrm{suf}[u]<K$ ：即使全选剩余项目也不够，属于不可行。
$\mathrm{cnt}\ge \mathrm{ans}$ ：现有项目数已不优于已找到的答案，继续选也不能改善最少数量。

最后一条依赖“未来数量不会减少”，不是任意最值题都能用“当前不如最好就停止”。

在决策树中，剪枝表示不再展开当前节点下面的整棵子树。因此需要证明这棵子树中的所有后续选择都无法贡献所需答案，而不只是当前这一条路径暂时不理想。

7.2 核心代码

const int N=25;
int n,ans;
long long K,a[N],suf[N];
void dfs(int u,long long sum,int cnt){
	if(sum>=K){
		ans=min(ans,cnt);
		return;
	}
	if(u==n+1||cnt>=ans||sum+suf[u]<K)return;
	dfs(u****um+a[u],cnt+1);
	dfs(u****um,cnt);
}
int minItems(){
	suf[n+1]=0;
	for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];
	ans=n+1;
	dfs(1,0,0);
	return ans==n+1?-1:ans;
}

调用方式： 读入数据后，答案为 minItems()。

本题只求最小数量；若要统计所有最优方案，不能直接沿用会剪掉等优分支的判断。

8. DFS 解题方法总结

前面的案例分别让我们处理了选取、排列、路径与最优方案。现在回过头，把这些做法归纳成四个共同问题。

问题	要写清的内容
当前状态	已处理到哪里？已经使用哪些资源？
合法选择	下一步允许做什么？
结束条件	怎样判断方案已经完整？
返回处理	哪些共享数据要恢复，才能继续尝试其他分支？

回顾前面的六个案例，每个 DFS 都可以先用这四个问题说明白，再落实到参数、分支和返回处理。参数不必一开始就追求最少，应先准确表达题意。

8.1 搜索与剪枝的基本步骤

先写出能正确枚举小规模答案的版本，再添加剪枝。每加一条剪枝，都问自己：

被放弃的分支，为什么不可能贡献所需的答案？

搜索也可以用来产生小数据的标准答案，检验后续 DP 是否正确。但对拍只能帮助发现错误，不能代替算法说明。

9. DFS 的时间与空间复杂度

理解案例之后，再分析程序需要做多少工作。此时可以对照搜索分支，说明为什么有些问题只能处理很小的数据。

9.1 复杂度分析的基本方法

DFS 是探索顺序，具体复杂度取决于访问多少状态、每个状态做多少工作。

遍历普通图，每个点只处理一次、每条边只检查常数次，邻接表实现通常为 $O(n+m)$ 。
枚举 $n$ 件物品选或不选，会产生 $2^{n}$ 个完整方案。
枚举 $n$ 个不同对象的排列，会产生 $n!$ 个完整方案。

不能仅看到函数名叫 $\mathrm{dfs}$ ，就断定复杂度；也不能只看代码中有一个 for，就断定为 $O(n)$ 。

9.2 例题复杂度对照

例题	主要工作量	时间或输出量分析	辅助空间
D1：输出所有参加名单	枚举所有选与不选的决定串，并逐项输出	有 $2^{n}$ 个方案，单个方案最多输出 $n$ 个编号，总时间 $O(n\cdot 2^{n})$	$O(n)$
D2：统计恰好用时的方案	搜索选与不选的分支	最坏时间 $O(2^{n})$	$O(n)$
D3：输出代表组合	访问组合搜索树，并输出组合	有 $\binom{n}{m}$ 个组合；输出编号的工作量为 $m\cdot \binom{n}{m}$ ，另需计算中间节点的枚举工作； $m=0$ 时输出一次空方案	$O(n)$
D4：输出所有排列	枚举排列并输出	有 $n!$ 个排列，每个输出 $n$ 个编号，总时间 $O(n\cdot n!)$	$O(n)$
D5：统计迷宫简单路径	枚举不同的合法路径前缀	若可走格子数为 $q$ ，深度至多为 $q$ ，可用 $O(4^{q})$ 作粗略时间上界	$O(nm)$
D6：最少项目数量	搜索选与不选的分支，并维护当前最优值	最坏时间 $O(2^{n})$	$O(n)$

D3 的组合数是完整答案的数量，不应只看这个数量就忽略中间节点的搜索开销。D5 的上界比较宽松，用来说明路径枚举可能指数增长，不代表每个网格都会达到这个数量。

9.3 剪枝对运行效率的影响

D2 和 D6 都加入了剪枝，但在某些输入下仍可能访问大量分支。不能因为程序中出现几条 return，就直接把指数级算法写成 $O(n)$ 。

估算时可以按三个步骤检查：

有多少完整方案，或多少个会实际访问的状态？
每个状态要枚举多少选择、完成多少额外工作？
是否还要输出完整方案，递归最深会走多少层？

空间分析还要考虑递归调用栈。例如排列搜索即使只用一个 $\mathrm{path}$ 数组，也同时保留了多层尚未返回的函数调用。

9.4 DFS 与二进制枚举

课纲中的二进制枚举可以作为选取问题的另一种写法： $n$ 位分别表示 $n$ 个选择，枚举 $0$ 到 $2^{n}-1$ 。它与 D1 的决定串对应；DFS 更方便在中间层提前停止，二进制枚举则通常更直接。

DFS 枚举的状态数不是越少越好，而是要在保证不漏解的前提下减少无用工作。完成本篇后，下一篇《基础线性动态规划》将从决策树中的重复子问题切入，学习记忆化搜索与动态规划。

有帮助，赞一个

去预览

0/2000

这里空空如也