做的网站一定要收录么,专业建设网站外包,陕西整站关键词自然排名优化,网页怎么画dfs 与 bfs 区别
提到深度优先搜索#xff08;dfs#xff09;#xff0c;就不得不说和广度优先搜索#xff08;bfs#xff09;有什么区别
先来了解dfs的过程#xff0c;很多录友可能对dfs#xff08;深度优先搜索#xff09;#xff0c;bfs#xff08;广度优先搜索…dfs 与 bfs 区别
提到深度优先搜索dfs就不得不说和广度优先搜索bfs有什么区别
先来了解dfs的过程很多录友可能对dfs深度优先搜索bfs广度优先搜索分不清。
先给大家说一下两者大概的区别
dfs是可一个方向去搜不到黄河不回头直到遇到绝境了搜不下去了再换方向换方向的过程就涉及到了回溯。bfs是先把本节点所连接的所有节点遍历一遍走到下一个节点的时候再把连接节点的所有节点遍历一遍搜索方向更像是广度四面八方的搜索过程。
深度优先dfs
深度优先关键就两点
搜索方向是认准一个方向搜直到碰壁之后再换方向换方向是撤销原路径改为节点链接的下一个路径回溯的过程。
其实深搜和回溯是非常类似的深搜三部曲如下 1.确认递归函数参数
void dfs(参数)通常我们递归的时候我们递归搜索需要了解哪些参数其实也可以在写递归函数的时候发现需要什么参数再去补充就可以。
一般情况深搜需要 二维数组数组结构保存所有路径需要一维数组保存单一路径这种保存结果的数组我们可以定义一个全局变量避免让我们的函数参数过多。
vectorvectorint result; // 保存符合条件的所有路径
vectorint path; // 起点到终点的路径
void dfs (图目前搜索的节点)
2.确认 终止条件
终止条件很重要很多同学写dfs的时候之所以容易死循环栈溢出等等这些问题都是因为终止条件没有想清楚。
if (终止条件) {存放结果;return;
}终止添加不仅是结束本层递归同时也是我们收获结果的时候。
另外其实很多dfs写法没有写终止条件其实终止条件写在了 下面dfs递归的逻辑里了也就是不符合条件直接不会向下递归。 3.处理目前搜索节点出发的路径
一般这里就是一个for循环的操作去遍历 目前搜索节点 所能到的所有节点。
for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果
}
797.所有可能的路径
力扣题目链接(opens new window)
给你一个有 n 个节点的 有向无环图DAG请你找出所有从节点 0 到节点 n-1 的路径并输出不要求按特定顺序
graph[i] 是一个从节点 i 可以访问的所有节点的列表即从节点 i 到节点 graph[i][j]存在一条有向边。 提示
n graph.length2 n 150 graph[i][j] ngraph[i][j] ! i即不存在自环graph[i] 中的所有元素 互不相同保证输入为 有向无环图DAG 思路深度优先基础题目 class Solution {
public:vectorvectorintresult;vectorintpath;void dfs(vectorvectorint graph, int x){if(xgraph.size()-1){//搜索到终点停止搜索并把可行路径加入结果数组result.push_back(path);return;}for(int i0; igraph[x].size(); i){//遍历节点所能访问的所有其他节点path.push_back(graph[x][i]);dfs(graph, graph[x][i]);//递归遍历path.pop_back();//回溯}}vectorvectorint allPathsSourceTarget(vectorvectorint graph) {result.clear();path.clear();path.push_back(0);//从0节点出发dfs(graph,0);//从节点0开始搜索return result;}
}; 广度优先搜索理论基础
广度优先类似于二叉树的层序遍历
广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发以起始点为中心一圈一圈进行搜索一旦遇到终点记录之前走过的节点就是一条最短路。
上面我们提过BFS是一圈一圈的搜索过程但具体是怎么一圈一圈来搜呢。
我们用一个方格地图假如每次搜索的方向为 上下左右不包含斜上方那么给出一个start起始位置那么BFS就是从四个方向走出第一步。 如果加上一个end终止位置那么使用BFS的搜索过程如图所示 我们从图中可以看出从start起点开始是一圈一圈向外搜索方格编号1为第一步遍历的节点方格编号2为第二步遍历的节点第四步的时候我们找到终止点end。
正是因为BFS一圈一圈的遍历方式所以一旦遇到终止点那么一定是一条最短路径。 大家应该好奇这一圈一圈的搜索过程是怎么做到的是放在什么容器里才能这样去遍历。
很多网上的资料都是直接说用队列来实现。
其实我们仅仅需要一个容器能保存我们要遍历过的元素就可以那么用队列还是用栈甚至用数组都是可以的。
用队列的话就是保证每一圈都是一个方向去转例如统一顺时针或者逆时针。
因为队列是先进先出加入元素和弹出元素的顺序是没有改变的。
如果用栈的话就是第一圈顺时针遍历第二圈逆时针遍历第三圈有顺时针遍历。
因为栈是先进后出加入元素和弹出元素的顺序改变了。
那么广搜需要注意 转圈搜索的顺序吗 不需要
所以用队列还是用栈都是可以的但大家都习惯用队列了所以下面的讲解用我也用队列来讲只不过要给大家说清楚并不是非要用队列用栈也可以。
广搜代码模板该模板针对的就是上面的四方格的地图 详细注释 int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图也就是一个二维数组
// visited标记访问过的节点不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] true; // 只要加入队列立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pairint ,int cur que.front(); que.pop(); // 从队列取元素int curx cur.first;int cury cur.second; // 当前节点坐标for (int i 0; i 4; i) { // 开始想当前节点的四个方向左右上下去遍历int nextx curx dir[i][0];int nexty cury dir[i][1]; // 获取周边四个方向的坐标if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue; // 坐标越界了直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] true; // 只要加入队列立刻标记避免重复访问}}}} 200. 岛屿数量
题目链接(opens new window)
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。 提示
m grid.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 0 或 1‘
广度优先版本
class Solution {
public:int dir[4][2]{0,1,1,0,-1,0,0,-1};//定义四个方向void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y){queuepairint,int que;que.push({x,y});while(!que.empty()){pairint, int curque.front(); que.pop();//出队访问int curxcur.first;int cury cur.second;visited[curx][cury]true;//标记该节点访问过for(int i0;i4;i){int nextxcurxdir[i][0];int nextycurydir[i][1];//判断是否超出边界if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size())continue;if(!visited[nextx][nexty]grid[nextx][nexty]1){que.push({nextx,nexty});visited[nextx][nexty]true;}}}}int numIslands(vectorvectorchar grid) {int result0;int ngrid.size();int mgrid[0].size();vectorvectorboolvisited(n, vector(m,false));for(int i0;in;i){for(int j0;jm;j){if(!visited[i][j]grid[i][j]1){result;bfs(grid,visited,i,j );}}}return result;}
}; 深度优先版本
class Solution {
public:int dir[4][2]{0,1,1,0,-1,0,0,-1};//定义四个方向void dfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y){for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size())continue;if(!visited[nextx][nexty]grid[nextx][nexty]1){visited[nextx][nexty]true;dfs(grid,visited,nextx,nexty);}}}int numIslands(vectorvectorchar grid) {int result0;int ngrid.size();int mgrid[0].size();vectorvectorboolvisited(n, vector(m,false));for(int i0;in;i){for(int j0;jm;j){if(!visited[i][j]grid[i][j]1){result;dfs(grid,visited,i,j );}}}return result;}
}; 参考代码随想录
