文章目录深度优先搜索理论基础dfs 与 bfs 区别dfs搜索过程代码框架dfs三部曲【98.可达路径】图的存储方式邻接矩阵邻接表广度优先搜索理论基础广搜的使用场景广搜的过程代码框架深度优先搜索理论基础dfs 与 bfs 区别dfs是可一个方向去搜不到黄河不回头直到遇到绝境了搜不下去了再换方向换方向的过程就涉及到了回溯。bfs是先把本节点所连接的所有节点遍历一遍走到下一个节点的时候再把连接节点的所有节点遍历一遍搜索方向更像是广度四面八方的搜索过程。dfs搜索过程关键就两点搜索方向是认准一个方向搜直到碰壁之后再换方向换方向是撤销原路径改为节点链接的下一个路径回溯的过程。代码框架正是因为dfs搜索可一个方向并需要回溯所以用递归的方式来实现是最方便的。有递归的地方就有回溯那么回溯在哪里呢就递归函数的下面例如如下代码voiddfs(参数){处理节点dfs(图选择的节点);// 递归回溯撤销处理结果}可以看到回溯操作就在递归函数的下面递归和回溯是相辅相成的。在讲解二叉树章节的时候二叉树的递归法其实就是dfs而二叉树的迭代法就是bfs广度优先搜索所以dfsbfs其实是基础搜索算法也广泛应用与其他数据结构与算法中。再回顾一下回溯法的代码框架voidbacktracking(参数){if(终止条件){存放结果;return;}for(选择本层集合中元素树中节点孩子的数量就是集合的大小){处理节点;backtracking(路径选择列表);// 递归回溯撤销处理结果}}回溯算法其实就是dfs的过程以下给出dfs的代码框架voiddfs(参数){if(终止条件){存放结果;return;}for(选择本节点所连接的其他节点){处理节点;dfs(图选择的节点);// 递归回溯撤销处理结果}}可以发现dfs的代码框架和回溯算法的代码框架是差不多的。以下再用深搜三部曲来解读 dfs的代码框架。dfs三部曲确认递归函数参数voiddfs(参数)通常我们递归的时候我们递归搜索需要了解哪些参数其实也可以在写递归函数的时候发现需要什么参数再去补充就可以。一般情况深搜需要二维数组结构保存所有路径需要一维数组保存单一路径这种保存结果的数组我们可以定义一个全局变量避免让我们的函数参数过多。例如这样vectorvectorintresult;// 保存符合条件的所有路径vectorintpath;// 起点到终点的路径voiddfs(图目前搜索的节点)但这种写法看个人习惯不强求。确认终止条件终止条件很重要很多时候写dfs的时候之所以容易死循环栈溢出等等这些问题都是因为终止条件没有想清楚。if(终止条件){存放结果;return;}终止添加不仅是结束本层递归同时也是我们收获结果的时候。另外其实很多dfs写法没有写终止条件是因为终止条件写在了隐藏在下面dfs递归的逻辑里了也就是如果不符合条件直接不会向下递归。后面会有具体题目来讲解。处理目前搜索节点出发的路径一般这里就是一个for循环的操作去遍历 目前搜索节点 所能到的所有节点。for(选择本节点所连接的其他节点){处理节点;dfs(图选择的节点);// 递归回溯撤销处理结果}那为什么都是 dfs代码框架中for循环里分明已经处理节点了dfs函数下面还要撤销呢。如下图所示路径2已经走到了目的地节点6那么路径2是如何撤销然后改为路径3呢 其实这就是回溯的过程撤销路径2换下一个方向。【98.可达路径】图的存储方式邻接矩阵邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图有多少节点就申请多大的二维数组。本题我们会有n 个节点因为节点标号是从1开始的为了节点标号和下标对齐我们申请 n 1 * n 1 这么大的二维数组。vectorvectorintgraph(n1,vectorint(n1,0));输入m个边构造方式如下while(m--){cinst;// 使用邻接矩阵 1 表示 节点s 指向 节点tgraph[s][t]1;}邻接表邻接表 使用 数组 链表的方式来表示。 邻接表是从边的数量来表示图有多少边 才会申请对应大小的链表。邻接表的构造相对邻接矩阵难理解一些。以下图为例这里表达的图是节点1 指向 节点3 和 节点5节点2 指向 节点4、节点3、节点5节点3 指向 节点4节点4指向节点1我们需要构造一个数组数组里的元素是一个链表。C写法// 节点编号从1到n所以申请 n1 这么大的数组vectorlistintgraph(n1);// 邻接表list为C里的链表输入m个边构造方式如下while(m--){cinst;// 使用邻接表 表示 s - t 是相连的graph[s].push_back(t);}本题我们使用邻接表 或者 邻接矩阵都可以因为后台数据并没有对图的大小以及稠密度做很大的区分。以下我们使用邻接矩阵的方式来讲解文末也会给出 使用邻接表的整体代码。注意邻接表 和 邻接矩阵的写法都要掌握// 邻接矩阵写法#includeiostream#includevectorusingnamespacestd;vectorvectorintresult;// 收集符合条件的路径vectorintpath;// 1节点到终点的路径// x目前遍历的节点// graph存当前的图// n终点voiddfs(constvectorvectorintgraph,intx,intn){if(xn){result.push_back(path);return;}for(inti1;in;i){// 遍历节点x链接的所有节点if(graph[x][i]1){// 找到x链接的节点ipath.push_back(i);// 将i放入path中dfs(graph,i,n);// 进行dfspath.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);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;}}// 邻接矩阵写法#includeiostream#includevector#includelistusingnamespacestd;vectorvectorintresult;// 收集符合条件的路径vectorintpath;// 1节点到终点的路径// x目前遍历的节点// graph存当前的图// n终点voiddfs(constvectorlistintgraph,intx,intn){if(xn){result.push_back(path);return;}for(inti:graph[x]){// 遍历节点x链接的所有节点ipath.push_back(i);// 将i加入path中dfs(graph,i,n);// 进入下一层递归path.pop_back();// 回溯 撤销本节点}}intmain(){intn,m,s,t;cinnm;// 节点编号从1-n所以申请n1这么大的数组vectorlistintgraph(n1);while(m--){cinst;// 使用邻接表表示无向图graph[s].push_back(t);}path.push_back(1);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;}}广度优先搜索理论基础广搜bfs是一圈一圈的搜索过程和深搜dfs是一条路跑到黑然后再回溯。广搜的使用场景广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发以起始点为中心一圈一圈进行搜索一旦遇到终点记录之前走过的节点就是一条最短路。当然也有一些问题是广搜 和 深搜都可以解决的例如岛屿问题这类问题的特征就是不涉及具体的遍历方式只要能把相邻且相同属性的节点标记上就行。 我们会在具体题目讲解中详细来说广搜的过程上面我们提过BFS是一圈一圈的搜索过程但具体是怎么一圈一圈来搜呢。我们用一个方格地图假如每次搜索的方向为 上下左右不包含斜上方那么给出一个start起始位置那么BFS就是从四个方向走出第一步。如果加上一个end终止位置那么使用BFS的搜索过程如图所示从图中可以看出从start起点开始是一圈一圈向外搜索方格编号1为第一步遍历的节点方格编号2为第二步遍历的节点第四步的时候我们找到终止点end。正是因为BFS一圈一圈的遍历方式所以一旦遇到终止点那么一定是一条最短路径。而且地图还可以有障碍如图所示在第五步第六步 只把关键的节点染色了其他方向周边没有去染色大家只要关注关键地方染色的逻辑就可以。从图中可以看出如果添加了障碍我们是第六步才能走到end终点。只要BFS只要搜到终点一定是一条最短路径大家可以参考上面的图自己再去模拟一下。代码框架大家应该好奇这一圈一圈的搜索过程是怎么做到的是放在什么容器里才能这样去遍历。很多网上的资料都是直接说用队列来实现。其实我们仅仅需要一个容器能保存我们要遍历过的元素就可以那么用队列还是用栈甚至用数组都是可以的。用队列的话就是保证每一圈都是一个方向去转例如统一顺时针或者逆时针。「统一顺时针 / 逆时针」只是遍历邻居的统一习惯不是 BFS 必须遵守的规则只有你需要沿着图形边缘连续绕圈时才强制要求方向顺序。所以建议直接统一顺时针/逆时针遍历是更通用的写法因为队列是先进先出加入元素和弹出元素的顺序是没有改变的。如果用栈的话就是第一圈顺时针遍历第二圈逆时针遍历第三圈有顺时针遍历。因为栈是先进后出加入元素和弹出元素的顺序改变了。那么广搜需要注意 转圈搜索的顺序吗 不需要所以用队列还是用栈都是可以的但还是用习惯的队列来说只不过大家要清楚并不是非要用队列用栈也可以。下面给出广搜代码模板该模板针对的就是上面的四方格的地图intdir[4][2]{0,1,1,0,0,-1,-1,0};// 表示四个方向// grid 是地图也就是一个二维数组// visited标记访问过的节点不要重复访问// x,y 表示开始搜索节点的下标voidbfs(vectorvectorchargrid,vectorvectorboolvisited,intx,inty){queuepairint,intque;// 定义队列que.push({x,y});// 起始节点加入队列visited[x][y]true;// 只要加入队列立刻标记为访问过的节点while(!que.empty()){// 开始遍历队列里的元素pairint,intcurque.front();que.pop();// 从队列取元素intcurxcur.first;intcurycur.second;// 当前节点坐标for(inti0;i4;i){// 开始向当前节点的四个方向右、下、左、上去遍历intnextxcurxdir[i][0];intnextycurydir[i][1];// 获取周边四个方向的坐标if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size())continue;// 坐标越界了直接跳过if(!visited[nextx][nexty]){// 如果节点没被访问过que.push({nextx,nexty});// 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty]true;// 只要加入队列立刻标记避免重复访问}}}}