深度优先搜索（dfs）

深度优先搜索1 什么是图的遍历图的遍历Graph Traversal指的是从图中的某一个顶点开始按照一定规则访问图中的所有顶点并且每个顶点只访问一次的过程。简单理解就像在一个由很多点和线组成的网络里按某种顺序把所有点都走一遍。2.深度优先搜索理论基础深度优先搜索DFSDepth First Search是一种图的遍历算法它从一个节点出发沿着每一条边一直深入到不能继续的地方再回溯到最近的一个有未被探索的邻接节点的节点继续深度搜索直到所有节点都被访问。从顶点0开始有两个顶点可以继续往下遍历1,2两个任选其一进行访问假设选择顶点1接下来有3个选择我们知道回到顶点0无意义因为我们已经访问过他了所以我们选择新的顶点来访问那么我们访问顶点2顶点2有两个选择顶点0或1但他们都被访问过所以这里我们无法继续往下了只能原路退一步回到顶点1深度优先搜索DFS的回退路径必须按照它原来的遍历路径返回。原因是 DFS 的回退本质上依赖 栈结构或递归调用栈而栈的特点是 后进先出LIFO。也就是说你是从哪条路径走进去的就必须沿着那条路径退回来。从顶点1开始我们还有两个未探索过得顶点即顶点3和顶点4我们访问顶点3从顶点3出发只能到达顶点5所以我们访问顶点5从顶点5出发可以访问6、7、8继续访问顶点6现在有到达了一个死胡同类似顶点2所以我们要后退一步到达顶点5接下来选择顶点7开始访问从顶点7出发访问的唯一路径是顶点8从顶点8出发访问的唯一路径只有一条路选择访问顶点9到达顶点9后进入了死胡同所以回到顶点8因为我们已经访问过了顶点8的所有顶点所以同理我们再次回退一步回到顶点77也被访问过回退一步到达顶点5顶点5也都被访问过所以我们回退到顶点3相同的回退到顶点1发现顶点4未被访问我们访问顶点4到达顶点4后无其他未访问过的节点了所以我们回退到顶点1顶点1也没有未访问过的节点了最后我们回退到了出发顶点0完成遍历我们会一直访问新的节点直到遇到死胡同深度优先搜索的序列并不唯一在多个顶点可访问时我们可以选择不同的顶点来生成另外一个序列最好始终选择较小值的节点3.代码框架正是因为dfs搜索可一个方向并需要回溯所以用递归的方式来实现是最方便的。就递归函数的下面例如如下代码voiddfs(参数){处理节点dfs(图选择的节点);// 递归回溯撤销处理结果}可以看到回溯操作就在递归函数的下面递归和回溯是相辅相成的。我们在回顾一下回溯法的代码框架voidbacktracking(参数){if(终止条件){存放结果;return;}for(选择本层集合中元素树中节点孩子的数量就是集合的大小){处理节点;backtracking(路径选择列表);// 递归回溯撤销处理结果}}回溯算法其实就是dfs的过程这里给出dfs的代码框架voiddfs(参数){if(终止条件){存放结果;return;}for(选择本节点所连接的其他节点){处理节点;dfs(图选择的节点);// 递归回溯撤销处理结果}}可以发现dfs的代码框架和回溯算法的代码框架是差不多的。4.DFS基本步骤确认递归函数参数voiddfs(参数)通常我们递归的时候我们递归搜索需要了解哪些参数其实也可以在写递归函数的时候发现需要什么参数再去补充就可以。一般情况深搜需要 二维数组数组结构保存所有路径需要一维数组保存单一路径这种保存结果的数组我们可以定义一个全局变量避免让我们的函数参数过多。例如这样vectorvectorintresult;// 保存符合条件的所有路径vectorintpath;// 起点到终点的路径voiddfs(图目前搜索的节点)确认终止条件终止条件很重要很多时候写dfs的时候之所以容易死循环栈溢出等等这些问题都是因为终止条件没有想清楚。if(终止条件){存放结果;return;}终止添加不仅是结束本层递归同时也是我们收获结果的时候。另外其实很多dfs写法没有写终止条件其实终止条件写在了 隐藏在下面dfs递归的逻辑里了也就是不符合条件直接不会向下递归。处理目前搜索节点出发的路径一般这里就是一个for循环的操作去遍历 目前搜索节点 所能到的所有节点。for(选择本节点所连接的其他节点){处理节点;dfs(图选择的节点);// 递归回溯撤销处理结果}5.DFS例题所有可达路径对应题目代码随想录卡码网所有可达路径力扣7975.1题目5.2思路深搜三部曲来分析题目确认递归函数参数首先我们dfs函数一定要存一个图用来遍历的需要存一个目前我们遍历的节点定义为x。还需要存一个n表示终点我们遍历的时候用来判断当 xn 时候 标明找到了终点。其实在递归函数的参数 不容易一开始就确定了一般是在写函数体的时候发现缺什么参加就补什么至于 单一路径 和 路径集合 可以放在全局变量那么代码是这样的vectorvectorintresult;// 收集符合条件的路径vectorintpath;// 0节点到终点的路径// x目前遍历的节点// graph存当前的图// n终点voiddfs(constvectorvectorintgraph,intx,intn)确认终止条件什么时候我们就找到一条路径了当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。// 当前遍历的节点x 到达节点nif(xn){// 找到符合条件的一条路径result.push_back(path);return;}处理目前搜索节点出发的路径接下来是走 当前遍历节点x的下一个节点。首先是要找到 x节点指向了哪些节点呢 遍历方式是这样的for(inti1;in;i){// 遍历节点x链接的所有节点if(graph[x][i]1){// 找到 x指向的节点就是节点i}}接下来就是将 选中的x所指向的节点加入到 单一路径来。path.push_back(i);// 遍历到的节点加入到路径中来进入下一层递归dfs(graph,i,n);// 进入下一层递归最后就是回溯的过程撤销本次添加节点的操作。该过程整体代码or(inti1;in;i){// 遍历节点x链接的所有节点if(graph[x][i]1){// 找到 x链接的节点path.push_back(i);// 遍历到的节点加入到路径中来dfs(graph,i,n);// 进入下一层递归path.pop_back();// 回溯撤销本节点}}5.3 完整代码#includeiostream#includevectorusingnamespacestd;vectorvectorintresult;// 收集符合条件的路径vectorintpath;// 1节点到终点的路径voiddfs(constvectorvectorintgraph,intx,intn){// 当前遍历的节点x 到达节点nif(xn){// 找到符合条件的一条路径result.push_back(path);return;}for(inti1;in;i){// 遍历节点x链接的所有节点if(graph[x][i]1){// 找到 x链接的节点path.push_back(i);// 遍历到的节点加入到路径中来dfs(graph,i,n);// 进入下一层递归path.pop_back();// 回溯撤销本节点}}}intmain(){intn,m,s,t;cinnm;// 节点编号从1到n所以申请 n1 这么大的数组vectorvectorintgraph(n1,vectorint(n1,0));while(m--){cinst;// 使用邻接矩阵 表示无线图1 表示 s 与 t 是相连的graph[s][t]1;}path.push_back(1);// 无论什么路径已经是从0节点出发dfs(graph,1,n);// 开始遍历// 输出结果if(result.size()0)cout-1endl;for(constvectorintpa:result){for(inti0;ipa.size()-1;i){coutpa[i] ;}coutpa[pa.size()-1]endl;}}