引入
在日常 C++ 编程中,常会遇到 DFS(深度优先搜索)这一概念。本文介绍其定义、特点及实现方法。
定义
DFS(Depth First Search),即深度优先搜索,是一种利用计算机运行速度优势解决需要枚举较多情况问题的搜索方法。
算法特点
DFS 利用递归实现枚举,将问题逐步分层细化。在问题足够小时解决(终止条件),并将答案返回(回溯),类似分治思想。
算法实现
使用 DFS 时通常定义一个 dfs() 函数,包含参数如递归深度、当前状态等。完整 DFS 需具备以下三部分:
- 当前状态
- 递归边界
- 初始状态
例题
题目
将正整数 n 分解为 m 个正整数,排在后面的数必须大于等于前面的数,输出所有方案。 若不使用 DFS,可使用多重循环,但当 m 不确定时难以确定循环层数,此时 DFS 更为适用。
题目分析
定义 dfs 函数所需状态:
- 剩余可用的数字大小
- 前一个数字的大小(保证后一个数 >= 前一个数)
- 已分出的数字个数
函数签名建议:dfs(剩余可用数字,上一个数字大小,已分出数字个数)
初始状态设计
- 剩余可用数字:n
- 上一个数字:0
- 已分出数字个数:0
状态处理
记当前可分配数字大小为 L,上一个数字为 x,已分出个数为 d,当前选择数字为 cnt,答案数为 ans。 cnt 从 x 开始遍历。若 cnt > L,则后续必然超过,直接返回。若 cnt <= L,继续下一位:L 变为 L-cnt,d 变为 d+1,x 变为 cnt。
核心逻辑流程:
对于 dfs(L, x, d):
当 d = n 时:
如果满足条件(L=0): 处理答案 (ans++)
如果不满足条件(L!=0): return
当 d != n 时:
遍历每一种可能的结果 (cnt)
如果可行:接着往下处理 dfs(L-cnt, cnt, d+1)
如果不可行:return
对于 main() 函数:输入数据,开始 dfs(n, 0, 0)。
核心流程概括
DFS 核心框架包含三个部分:
- 递归边界(Base Case)
- 递归处理答案(Recursive Step)
- 初始状态(Initial Call)
针对不同题目需设计不同的状态并处理。

