文章目录

前言一、DFS执行过程二、DFS思考过程1.搜索顺序2.回溯3.剪枝 三、DFS常用模板（C++版）四、隐式图常见题型及解法五、参考：

---

前言

本文总结了一些常见的在隐式图上深搜的DFS题目

---

一、DFS执行过程

二、DFS思考过程

1.搜索顺序

DFS题目首先考虑搜索顺序，就是要找一种搜索顺序，能把各种情况都枚举出来（想想上面说到的搜索树，每一步对应一个节点以及其延伸出的子树）。

2.回溯

回溯说白了就是在一个dfs内，结束了调用的dfs，回到原来的进程。回溯回到原来的进程后，一般都要“恢复现场” 记住 , 一但你从一个深搜出来 ， 就马上恢复现场，就像事情没发生过一样。当然，不一定所有题目都要恢复现场，根据下面图来判断。

3.剪枝

剪枝就是把不必要的搜索进程砍掉

三、DFS常用模板（C++版）

dfs()//参数用来表示状态 { if(到达终点状态) { ...//根据题意添加 return; } if(越界或者是不合法状态) return; if(特殊状态)//剪枝 return ; for(扩展方式) { if(扩展方式所达到状态合法) { 修改操作;//根据题意来添加 标记； dfs（）； (还原标记)； //是否还原标记根据题意 //如果加上（还原标记）就是 回溯法 } } } 链接：https://www.acwing.com/blog/content/592/

四、隐式图常见题型及解法

五、参考：

https://www.acwing.com/blog/content/592/ https://www.acwing.com/blog/content/1834/