2. 深度优先搜索算法DFS2.1 定义/用途从初始状态出发沿着一条路径尽可能向深处探索走到无法继续前进时回溯到上一层尝试其他分支持续遍历状态空间寻找目标解的搜索算法。光看定义DFS和枚举有几分相似。实际上严格来讲DFS和暴力枚举的效率是相同的大O表示法但是搜索通常会带来更少的不必要情况列举从而加快速度。2.2 算法描述DFS的内容常被戏称为“一条路走到黑”这种算法不那么公式化一般需要具体情况具体分析。比如使用树结构表示所有可能的情况ABCDEFGHIJK那么DFS搜索的顺序就是A→B→F→G→H→C→I→D→J→K→EA\rightarrow B \rightarrow F \rightarrow G \rightarrow H \rightarrow C \rightarrow I \rightarrow D \rightarrow J \rightarrow K \rightarrow EA→B→F→G→H→C→I→D→J→K→E这和后面将会学到的DFS遍历树有些相像简单说就是是否找到节点节点满足条件继续DFS子节点回溯DFS通常使用递归实现。下面是伪代码模板还是树形图举例voiddfs(intstep){// 递归终点满足条件输出答案if(step目标)return;for(枚举每一种选择){// 做出选择vis[x]true;// 向下一层搜索dfs(step1);// 回溯撤销本次选择vis[x]false;}}一般情况下DFS函数总有个参数表示递归深度用来及时终止DFS。2.3 经典模板题2.3.1 例题1图遍历最简单DFS题目给定无向图从1号点出发遍历所有连通节点邻接表存储图代码位置2\template\dfs_chart.cpp#includeiostream#includevectorusingnamespacestd;vectorintedge[105];boolvis[105];voiddfs(intu){coutu ;vis[u]true;for(intv:edge[u]){if(!vis[v])dfs(v);}}intmain(){intn,m;cinnm;for(inti1;im;i){inta,b;cinab;edge[a].push_back(b);edge[b].push_back(a);}dfs(1);return0;}2.3.2迷宫DFS网格地图.空地#墙起点(1,1)终点(n,m)寻找是否存在通路网格DFS四个方向上下左右代码位置2\template\dfs_maze.cpp#includeiostreamusingnamespacestd;charmp[105][105];boolvis[105][105];intn,m;intdx[]{-1,1,0,0};intdy[]{0,0,-1,1};// x,y 当前坐标booldfs(intx,inty){// 越界碰到墙访问过 → 走不通if(x1||xn||y1||ym||mp[x][y]#||vis[x][y])returnfalse;// 到达终点if(xnym)returntrue;vis[x][y]true;// 四个方向尝试for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(dfs(nx,ny))returntrue;}// 四个方向全部走不通returnfalse;}intmain(){cinnm;for(inti1;in;i)cinmp[i]1;if(dfs(1,1))cout可以到达终点;elsecout无路可走;return0;}2.4 小结DFS核心注意点去重vis访问标记数组没有vis数组 → 出现环路无限递归→栈溢出RE。递归出口一定要写缺少出口无限递归直接运行错误。回溯什么时候用只遍历图/连通块不需要撤销标记枚举所有可行方案路径、选数字、排列搜索完一定要撤销标记visfalse。