第三课《时间倒流术》——回溯与恢复现场一、故事开始时间魔法师的考验1、小骑士 DFS 已经掌握了✅ 一条路走到底✅ 递归返回✅ 搜索树但是。2、算法王国最强大的魔法师♂️“回溯法师”又给出了新的挑战。3、魔法师说“真正厉害的搜索不只是会往前冲。”“更重要的是——”“回来以后世界还必须恢复原样”4、小骑士有疑问的说“恢复原样”5、今天。我们要学习DFS 的重要一环回溯Backtracking也就是恢复现场二、怎样才能“恢复现场”先看一个生活例子。1、鞋印故事小骑士进入迷宫。每走一步都会留下脚印。例如S → A → B脚印S A B2、后来。发现 B 是死路。于是返回 A3、问题来了如果B 的脚印还留着。后面的人会以为“这里已经走过了”4、于是。真正聪明的探险家会回来时擦掉脚印5、这就是回溯三、为什么 DFS 需要回溯1、因为DFS在“尝试所有可能”的要求下如果不恢复现场。后面的路线就会受到前面的影响2、这是 DFS初学者容易出错的地方很多初学者不理解“恢复现场”就会排列错路径错状态混乱四、经典问题全排列1、例如全排列是DFS 经典的问题2、问题有三个数字1 2 3要求输出所有排列。3、什么叫排列例如123 132 213 231 312 321顺序不同。都算不同排列。五、同学们先别急想如何写代码1、先想一下搜索树2、第一层先选第一个数字1 2 33、如果先选 1第二层还能选2 或 34、如果1 → 2第三层只能选3形成1235、搜索树长这样[] / | \ 1 2 3 / \ / \ / \ 2 3 1 3 1 2 | | | | | | 3 2 3 1 2 16、DFS 正在干什么其实就是在搜索树里走路六、正式进入代码参考代码#include iostream #include vector using namespace std; vectorint path; bool vis[10]; int n 3; void dfs() { // 已经选了3个数字 if(path.size() n) { for(int i 0; i path.size(); i) cout path[i]; cout endl; return; } // 尝试每个数字 for(int i 1; i n; i) { // 已经用过 if(vis[i]) continue; // 选择数字 path.push_back(i); // 标记使用 vis[i] true; // 搜索下一层 dfs(); // 恢复现场 vis[i] false; path.pop_back(); } } int main() { dfs(); return 0; }七、真正理解 DFS 的“四步动作”1、DFS 回溯四步法① 做选择path.push_back(i);意思选择当前数字。例如选1path[1]② 标记状态vis[i] true;表示这个数字已经被用了。否则后面还能重复选。例如111 222就错了。③ 进入下一层dfs();意思“继续往下选”④ 恢复现场最重要vis[i] false; path.pop_back();什么意思表示“撤销刚才的选择”例如当前[1,2]现在已经搜索结束。需要回到上一层于是pop_back();变回[1]2、这就是时间倒流术八、模拟程序运行过程1、开始[]2、选1[1]3、再选2[1,2]4、再选3[1,2,3]输出1235、现在开始回溯删除3变回[1,2]继续搜索别的可能。6、然后删除2变回[1]7、再尝试3形成[1,3]8、这就是DFS 回溯的过程九、 撤销选择是回溯的本质因为dfs();回溯真正核心是做选择 ↓ 递归 ↓ 撤销选择没有“撤销”就没有回溯十、DFS 回溯模板经典模板for(选择) { 做选择; dfs(); 撤销选择; }真正含义试试看 ↓ 继续搜 ↓ 回来 ↓ 恢复原样 ↓ 再试下一种十一、本课总结今天同学们学会了什么1、✅ 什么是回溯返回上一层前恢复现场2、✅ 为什么必须恢复现场否则后面的搜索会混乱。3、✅ DFS 回溯四步法① 做选择push_back② 标记状态vistrue③ 搜索下一层dfs()④ 恢复现场pop_back visfalse十二、课后挑战挑战1把1 2 3改成1 2 3 4输出4个数字的全部排列。挑战2统计一共有多少种排列。挑战3请孩子自己手动画出搜索树因为“搜索树画得出来”才是真正理解 DFS。下节课预告下一节⚔️《DFS勇者挑战赛》同学们将独立解决 DFS 问题包括迷宫排列连通块二维 DFS真正成为DFS 小骑士
GESP6级C++考试语法知识（二十三、深度优先搜索（三、回溯与恢复））
发布时间：2026/5/21 16:07:20
第三课《时间倒流术》——回溯与恢复现场一、故事开始时间魔法师的考验1、小骑士 DFS 已经掌握了✅ 一条路走到底✅ 递归返回✅ 搜索树但是。2、算法王国最强大的魔法师♂️“回溯法师”又给出了新的挑战。3、魔法师说“真正厉害的搜索不只是会往前冲。”“更重要的是——”“回来以后世界还必须恢复原样”4、小骑士有疑问的说“恢复原样”5、今天。我们要学习DFS 的重要一环回溯Backtracking也就是恢复现场二、怎样才能“恢复现场”先看一个生活例子。1、鞋印故事小骑士进入迷宫。每走一步都会留下脚印。例如S → A → B脚印S A B2、后来。发现 B 是死路。于是返回 A3、问题来了如果B 的脚印还留着。后面的人会以为“这里已经走过了”4、于是。真正聪明的探险家会回来时擦掉脚印5、这就是回溯三、为什么 DFS 需要回溯1、因为DFS在“尝试所有可能”的要求下如果不恢复现场。后面的路线就会受到前面的影响2、这是 DFS初学者容易出错的地方很多初学者不理解“恢复现场”就会排列错路径错状态混乱四、经典问题全排列1、例如全排列是DFS 经典的问题2、问题有三个数字1 2 3要求输出所有排列。3、什么叫排列例如123 132 213 231 312 321顺序不同。都算不同排列。五、同学们先别急想如何写代码1、先想一下搜索树2、第一层先选第一个数字1 2 33、如果先选 1第二层还能选2 或 34、如果1 → 2第三层只能选3形成1235、搜索树长这样[] / | \ 1 2 3 / \ / \ / \ 2 3 1 3 1 2 | | | | | | 3 2 3 1 2 16、DFS 正在干什么其实就是在搜索树里走路六、正式进入代码参考代码#include iostream #include vector using namespace std; vectorint path; bool vis[10]; int n 3; void dfs() { // 已经选了3个数字 if(path.size() n) { for(int i 0; i path.size(); i) cout path[i]; cout endl; return; } // 尝试每个数字 for(int i 1; i n; i) { // 已经用过 if(vis[i]) continue; // 选择数字 path.push_back(i); // 标记使用 vis[i] true; // 搜索下一层 dfs(); // 恢复现场 vis[i] false; path.pop_back(); } } int main() { dfs(); return 0; }七、真正理解 DFS 的“四步动作”1、DFS 回溯四步法① 做选择path.push_back(i);意思选择当前数字。例如选1path[1]② 标记状态vis[i] true;表示这个数字已经被用了。否则后面还能重复选。例如111 222就错了。③ 进入下一层dfs();意思“继续往下选”④ 恢复现场最重要vis[i] false; path.pop_back();什么意思表示“撤销刚才的选择”例如当前[1,2]现在已经搜索结束。需要回到上一层于是pop_back();变回[1]2、这就是时间倒流术八、模拟程序运行过程1、开始[]2、选1[1]3、再选2[1,2]4、再选3[1,2,3]输出1235、现在开始回溯删除3变回[1,2]继续搜索别的可能。6、然后删除2变回[1]7、再尝试3形成[1,3]8、这就是DFS 回溯的过程九、 撤销选择是回溯的本质因为dfs();回溯真正核心是做选择 ↓ 递归 ↓ 撤销选择没有“撤销”就没有回溯十、DFS 回溯模板经典模板for(选择) { 做选择; dfs(); 撤销选择; }真正含义试试看 ↓ 继续搜 ↓ 回来 ↓ 恢复原样 ↓ 再试下一种十一、本课总结今天同学们学会了什么1、✅ 什么是回溯返回上一层前恢复现场2、✅ 为什么必须恢复现场否则后面的搜索会混乱。3、✅ DFS 回溯四步法① 做选择push_back② 标记状态vistrue③ 搜索下一层dfs()④ 恢复现场pop_back visfalse十二、课后挑战挑战1把1 2 3改成1 2 3 4输出4个数字的全部排列。挑战2统计一共有多少种排列。挑战3请孩子自己手动画出搜索树因为“搜索树画得出来”才是真正理解 DFS。下节课预告下一节⚔️《DFS勇者挑战赛》同学们将独立解决 DFS 问题包括迷宫排列连通块二维 DFS真正成为DFS 小骑士
