OI-wiki 深度优先搜索（DFS）详解：从递归暴力枚举到回溯剪枝实战-北京尧图网络

OI-wiki 深度优先搜索DFS详解从递归暴力枚举到回溯剪枝实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文以 OI-wiki 搜索专题的 DFS搜索文档为骨架系统讲解算法竞赛中用递归函数实现暴力枚举的 DFS 搜索思想从分解整数这一经典分层决策问题出发推导出递归搜索的状态设计方法并给出 C/Python/Java 三语言完整实现随后结合全排列问题与回溯法的仓库源码深入剖析访问标记、回溯撤销、剪枝与边界条件等核心机制。读完本文你将掌握 DFS 搜索的分层决策建模套路、三语言模板代码以及将回溯技巧迁移到 N 皇后、迷宫计数等实战问题中的能力。引入搜索算法中的 DFS 是什么在 OI-wiki 中DFS图论讲解的是遍历树或图的深度优先算法而本文所在的搜索专题中DFS 一词则常常指利用递归函数方便地实现暴力枚举的算法——它与图论中的 DFS 有一定相似之处都以递归深度优先为特征但本质是对状态空间进行穷举通过穷尽所有可能来找到最优解或统计合法解的个数。搜索在 OI 中定位特殊它是很多高级算法的基础纯粹的搜索往往也是拿到部分分的手段但能靠纯搜索拿满分的题目非常少见 docs/search/index.md。因此掌握 DFS 的核心价值在于快速写出正确性有保障的暴力程序为剪枝、记忆化、双向搜索、迭代加深等优化见 docs/search/opt.md打下基础。问题引入从多重循环到递归搜索原文档用一个经典例题引出递归搜索的必要性把正整数 $n$ 分解为 $3$ 个正整数如 $6123$排在后面的数必须大于等于前面的数输出所有方案。三重循环解法当分解个数固定为 3 时直接三重循环即可参考实现如下for (int i 1; i n; i) for (int j i; j n; j) for (int k j; k n; k) if (i j k n) printf(%d %d %d %d\n, n, i, j, k);for i in range(1, n 1): for j in range(i, n 1): for k in range(j, n 1): if i j k n: print(%d %d %d %d % (n, i, j, k))for (int i 1; i n 1; i) { for (int j i; j n 1; j) { for (int k j; k n 1; k) { if (i j k n) System.out.printf(%d %d %d %d%n, n, i, j, k); } } }注意循环初值j i、k j正是排在后面的数大于等于前面的数这一约束的体现。循环嵌套的局限那如果是分解成四个整数呢再加一重循环那分解成小于等于 $m$ 个整数呢循环的层数写死在代码里当问题规模分解个数变为运行时输入时循环方案彻底失效。这正是递归搜索的用武之地。DFS 搜索的核心思想分层决策该类搜索算法的特点在于将要搜索的目标分成若干「层」每层基于前几层的状态进行决策直到达到目标状态。递归函数天然适合这种结构——递归的每一层调用恰好对应决策的一层。把分解正整数建模成分层决策考虑推广问题将正整数 $n$ 分解成不超过 $m$ 个正整数之和且排在后面的数必须大于等于前面的数输出所有方案。设一组方案将正整数 $n$ 分解成 $k$ 个正整数 $a_1, a_2, \ldots, a_k$ 的和。将问题分层第 $i$ 层决定 $a_i$。为了进行第 $i$ 层决策需要记录三个状态变量$n-\sum_{j1}^i a_j$剩余和表示后面所有正整数的和剩余 0 时说明已经凑出一个合法方案$a_{i-1}$前一层的正整数用于确保后一项 ≥ 前一项非降序$i$当前层号用于确保最多输出 $m$ 个正整数。为了记录方案用arr数组第 $i$ 项表示 $a_i$。注意到arr实际是一个长度为 $i$ 的栈——递归深入时写入新元素回溯时旧元素自然被覆盖无需显式弹出。递归实现三语言对照C 实现int m, arr[103]; // arr 用于记录方案 void dfs(int n, int i, int a) { if (n 0) { for (int j 1; j i - 1; j) printf(%d , arr[j]); printf(\n); } if (i m) { for (int j a; j n; j) { arr[i] j; dfs(n - j, i 1, j); // 请仔细思考该行含义 } } } // 主函数 scanf(%d%d, n, m); dfs(n, 1, 1);Python 实现arr [0] * 103 # arr 用于记录方案 def dfs(n, i, a): if n 0: print(arr[1:i]) if i m: for j in range(a, n 1): arr[i] j dfs(n - j, i 1, j) # 请仔细思考该行含义 # 主函数 n, m map(int, input().split()) dfs(n, 1, 1)Java 实现static int m; // arr 用于记录方案 static int[] arr new int[103]; public static void dfs(int n, int i, int a) { if (n 0) { for (int j 1; j i - 1; j) System.out.printf(%d , arr[j]); System.out.println(); } if (i m) { for (int j a; j n; j) { arr[i] j; dfs(n - j, i 1, j); // 请仔细思考该行含义 } } } // 主函数 final int N new Scanner(System.in).nextInt(); m new Scanner(System.in).nextInt(); dfs(N, 1, 1);关键一行的语义剖析原文档特意留下注释请仔细思考该行含义指的就是递归调用dfs(n - j, i 1, j);它的三个实参恰好对应前面设计的三个状态变量构成完整的状态转移参数含义传递方式n - j剩余和选走 $a_ij$ 后剩余待分解的和减少 $j$i 1层号进入下一层决策 $a_{i1}$j上一层的数保证下一层枚举从 $j$ 开始满足非降序约束而arr[i] j写入的是当前层的选择。当n 0时表示剩余和为 0方案恰好凑满此时arr[1..i-1]中存的就是一组合法分解直接输出。整个过程完全印证了每层基于前几层的状态进行决策的描述。复杂度直觉从整体看搜索空间是所有满足非降序的正整数序列枚举过程可以类比为构建一棵搜索树空间树。最坏情况下分支数与深度成正比地指数膨胀这也是 DFS 常搭配剪枝的原因——相关内容可参考 docs/basic/complexity.md 对时间复杂度的定义方式以及回溯法中的边界条件约束。实战例题全排列问题Luogu P1706原文档的例题部分给出了仓库内的完整代码引用对应文件为 docs/search/code/dfs/dfs_1.cpp。完整实现如下#include iomanip #include iostream using namespace std; int n; bool vis[50]; // 访问标记数组 int a[50]; // 排列数组按顺序储存当前搜索结果 void dfs(int step) { if (step n 1) { // 边界 for (int i 1; i n; i) { cout setw(5) a[i]; // 保留5个场宽 } cout endl; return; } for (int i 1; i n; i) { if (!vis[i]) { // 判断数字i是否在正在进行的全排列中 vis[i] true; a[step] i; dfs(step 1); vis[i] false; // 这一步不使用该数置0后允许下一步使用 } } return; } int main() { cin n; dfs(1); return 0; }逐层拆解这段模板代码这段代码是 DFS 搜索中极具代表性的排列型模板包含三个关键部件状态记录a[step]记录第step位放哪个数字vis[i]标记数字i是否已被使用边界条件step n 1表示已填满 $n$ 个位置此时输出一个完整排列setw(5)是 iomanip 提供的场宽控制输出每个数占 5 个字符宽度以对齐回溯撤销递归返回后执行vis[i] false把数字i释放允许其在兄弟分支中被再次使用——这一步是回溯走不通就回头的具象化。样例验证仓库配套测试数据给出了输入与期望输出见 docs/search/examples/dfs/dfs_1.in 与 dfs_1.ans。输入n 3时程序依次输出 6 个全排列1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1输出按字典序排列这正是从 1 到 n 顺序枚举候选带来的自然结果。对比分解整数与全排列两者都是 DFS 搜索但状态设计不同维度分解整数问题全排列问题每层决策什么决定 $a_i$ 的数值决定第step位放哪个数字约束来源后一项 ≥ 前一项非降序每个数字只能用一次vis标记完成判据剩余和n 0填满step n 1回溯操作覆盖arr[i]无需显式撤销显式vis[i] false释放数字可见 DFS 的通用框架是固定的——分层、记录状态、判边界、递归、回溯——不同的只是每道题的状态与约束定义。从 DFS 到回溯法搜索技巧的升华DFS 搜索常与回溯法搭配出现。OI-wiki 的回溯法文档指出回溯法是一种经常被用在深度优先搜索和广度优先搜索中的技巧其本质是**走不通就回头**。回溯法的标准过程为构造空间树进行遍历如遇到边界条件即不再向下搜索转而搜索另一条链达到目标条件输出结果。案例一N 皇后问题回溯标记数组回溯法的典型应用是 N 皇后。仓库中的实现见 docs/search/code/backtracking/backtracking_1.cpp核心部分// 该代码为回溯法的 DFS 实现 int ans[14], check[3][28] {0}, sum 0, n; void eq(int line) { if (line n) { // 如果已经搜索完n行 sum; if (sum 3) return; else { for (int i 1; i n; i) cout ans[i] ; cout \n; return; } } for (int i 1; i n; i) { if ((!check[0][i]) (!check[1][line i]) (!check[2][line - i n])) { // 判断在某位置放置是否合法 ans[line] i; check[0][i] 1; check[1][line i] 1; check[2][line - i n] 1; eq(line 1); // 向下递归后进行回溯方便下一轮递归 check[0][i] 0; check[1][line i] 0; check[2][line - i n] 0; } } }这个实现展示了 DFS 搜索的两种进阶技巧用标记数组代替暴力判断三个一维数组分别标记列check[0][i]、主对角线check[1][line i]同一主对角线行列常数与副对角线check[2][line - i n]同一副对角线行 − 列常数加n防止负数下标将放置合法性的判断从 $O(n)$ 扫描降为 $O(1)$ 查表边递归边回溯eq(line 1)递归返回后立即把三个标记清零恢复现场以供下一列尝试——这正是走不通就回头的代码形态。对应的 USACO 1.5.4 Checker Challenge 题目要求输出字典序前 3 个解与解的总数实现中sum 3之后直接返回即可停止输出同时继续计数。案例二迷宫路径计数DFS/BFS 皆可回溯法的另一类应用是迷宫方案计数。仓库提供了 docs/search/code/backtracking/backtracking_2.cpp其注释标明该代码为回溯法的 BFS 实现通过队列逐层扩展、用used数组记录路径占用状态来计数。这个例子说明搜索问题的层概念并不局限于递归——无论是递归函数的调用栈还是显式的队列/栈容器本质都是在维护状态空间上的遍历顺序。关于显式容器实现 DFS 的细节可参见 docs/graph/dfs.md 中的栈实现与递归实现两节——递归实现之所以等价于栈实现正是因为函数递归调用时的求值顺序与栈的压入/弹出顺序一致函数调用栈。搜索的优化方向原文档所在专题 docs/search/index.md 明确指出搜索有很多优化方式如减小状态空间、更改搜索顺序、剪枝等。结合上文可以归纳出三条递进思路减小状态空间尽可能让状态携带最少的信息。例如分解整数用剩余和上一数层号三个变量即可完整刻画无需额外记录已选数字列表更改搜索顺序全排列代码从 1 到 n 顺序枚举自然得到字典序输出按题设调整枚举顺序可配合剪枝提前命中目标剪枝在递归入口处用边界条件提前终止不可能产生合法解的分支。N 皇后中判断放置是否合法不通过就continue就是最朴素的剪枝更系统的优化可参考专题中的搜索优化、迭代加深、启发式搜索、A* 与 IDA* 等文档。总结DFS搜索的核心结论可以浓缩为一句话用递归把枚举几层循环抽象成按层决策。本文沿着 OI-wiki 原文档的脉络完成了从多重循环到递归搜索的动机推演、三层状态变量的建模、三语言模板实现并借助仓库内全排列与 N 皇后源码把访问标记、回溯撤销、$O(1)$ 合法性与剪枝等实战细节一一落到实处。掌握这套分层状态边界回溯的思维框架后无论是暴力对拍、搜索优化还是后续学习图论 DFS、强连通分量见 docs/graph/scc.md你都将拥有坚实的起点。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

OI-wiki 深度优先搜索（DFS）详解：从递归暴力枚举到回溯剪枝实战

相关推荐

放开那三国2祝福语讯飞输入法文件处理

Claude 也能直接生成 AI 短视频？用 Ace Data Cloud MCP 接入 Seedance

Hindsight 记忆接入选型指南：MCP 与 SDK 两种集成路径的源码级对比

更多资讯

ToolJet 访问控制（Access Control）完全指南：从工作区权限到细粒度资源授权

Rust 编译器 macOS 目标平台（*-apple-darwin）完整支持指南

Megatron-LM 多 Token 预测（MTP）：原理、配置与流水线布局实践指南

纯CNN图像分类新选择：MogaNet多阶博弈交互实战解析

医院预约挂号系统Java源码解析：号源并发与防超卖设计

mold 中的 Rust 符号反修饰：rust-demangle.c 单文件 C99 移植版解析

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？