免费网站后台模板,创造网址,龙岩网红郭建平,珠海酒店网站建设BFS#xff0c;也就是广度#xff08;宽度#xff09;优先搜索#xff0c;二叉树的层序遍历就是一个BFS的过程。而前、中、后序遍历则是DFS#xff08;深度优先搜索#xff09;。从字面意思也很好理解#xff0c;DFS就是一条路走到黑#xff0c;BFS则是一层一层地展开。… BFS也就是广度宽度优先搜索二叉树的层序遍历就是一个BFS的过程。而前、中、后序遍历则是DFS深度优先搜索。从字面意思也很好理解DFS就是一条路走到黑BFS则是一层一层地展开。 关于二叉树的创建与遍历大家可以参考下文 二叉树创建和遍历_二叉树的建立与遍历-CSDN博客 下图分别是DFS和BFS的遍历顺序图解 一、层序遍历
接下来我们直接来看题从题中感受BFS的魅力。 N叉树与二叉树的区别无非就是二叉树最多只有两个子节点用left和right两个指针就够储存。而N叉树有N多个节点需要一个指针数组来储存。 在用BFS解决问题时几乎都要借助队列结构用队列的先进先出特性来储存上一层的数据。 首先把根节点放到队列里面然后从队列里面取节点出来把节点取出来后通过它找到它的子节点并带入到队列里面。那么这个节点的使命就算完成了需要把它踢出队列。循环往复直到最后队列为空则完成层序遍历。 但对于这个题并不是简单的层序遍历就行它还要把每一层划分出来。这个其实也很简单只要记录每一层有几个节点记为n个然后一次性的遍历n个并把这n个元素用数组储存起来。可以直接使用size()计算该层元素个数。 代码示例
class Solution {
public:vectorvectorint levelOrder(Node* root){if(!root) return {};vectorvectorint ret;queueNode* qu;qu.push(root);while(!qu.empty()){vectorint arr;int nqu.size();//获取该层有一个元素while(n--)//取出该层的所以元素并把子节点带入{Node* rtqu.front();qu.pop();arr.push_back(rt-val);for(int i0;irt-children.size();i)qu.push(rt-children[i]);}if(!arr.empty()) ret.push_back(arr);} return ret;}
};
二、最短路问题 例如我们要找到从起点1到终点8的最短路径。
最终找到最短路如下
例题 首先因为它是上下左右式的扩散所以使用一个小技巧向量坐标
dx[4]{0,0,-1,1}dy[4]{-1,1,0,0};
我们使用 for(int k0;k4;k) x1 xdx[k], y1 ydy[k]; 就可以得到(x, y)的上下左右坐标的(x1, y1)。 它的扩展逻辑就和上文层序遍历中那一题差不多但需要一个变量记录层数。在扩展过程中需要判断是否是目标值还需要把扩展到的元素做标记。
代码示例
class Solution {
public:int dx[4]{0,0,-1,1},dy[4]{-1,1,0,0};int nearestExit(vectorvectorchar maze, vectorint entrance){int n maze.size(),m maze[0].size();vectorvectorbool hash(n,vectorbool(m));//记录是否已经搜索过queuepairint,int qu;qu.push({entrance[0],entrance[1]});hash[entrance[0]][entrance[1]] true;int ret 0;//记录层数while(!qu.empty()){ret;int sz qu.size();while(sz--){auto [a,b] qu.front();qu.pop();for(int k0;k4;k){int x adx[k],y bdy[k];if(x0xny0ym!hash[x][y]maze[x][y].){if(x0||xn-1||y0||ym-1) return ret;hash[x][y] true;qu.push({x,y});}}}}return -1;}
}; 这个题我们可以做一个多趟的BFS首先确定第一个起点和终点进行BFS搜索并记录路径长度。 注意由题可知没有两棵树的高度是相同的也就是说树的高度和它的坐标是一一对应的。
具体操作如下 把所有树的高度1的元素都记录到一个数组中然后对该数组进行排序。这样我们就知道搜索的先后顺序。 封装一个bfs函数如pairint,int bfs(int x,int y,int target,vectorvectorint forest)传入起点坐标与终点的值它的作用是记录起点到终点的最短距离然后返回终点的坐标。如果不能被搜索到返回{-1 -1}。 距离的计算我们可以使用一个全局变量在bfs中累加。 进行一次bfs后得到的返回值作为下一次搜索的起点下标而终点值从刚才排序好的数组中取到。 最后使用循环把数组中所有的值都搜索一遍。 class Solution {
public:int ret 0,m 0,n 0;int dx[4] {0,0,-1,1},dy[4]{-1,1,0,0};int cutOffTree(vectorvectorint forest){m forest.size(),n forest[0].size();vectorint arr;for(int i0;im;i)for(int j0;jn;j)if(forest[i][j]1) arr.push_back(forest[i][j]);sort(arr.begin(),arr.end());int x 0,y 0;for(int i0;iarr.size();i){if(i0arr[i]forest[0][0]) continue;auto [a,b] bfs(x,y,arr[i],forest);if(a-1) return -1;x a,y b;}return ret;}pairint,int bfs(int x,int y,int target,vectorvectorint forest){vectorvectorbool hash(m,vectorbool(n));queuepairint,int qu;qu.push({x,y});hash[x][y] true;while(!qu.empty()){ret;int sz qu.size();while(sz--){auto [a,b] qu.front();qu.pop();for(int k0;k4;k){int x1 adx[k],y1 bdy[k];if(x10x1my10y1n!hash[x1][y1]forest[x1][y1]!0){if(forest[x1][y1]target) return {x1,y1};hash[x1][y1]true;qu.push({x1,y1});}}}}return {-1,-1};}
};
三、多源最短路问题
多源最短路它的特点就是可以选择多个起点找出到达终点的最短路径。 其实它和单源最短路差别并不是很大我们只需要把所有起点看作一个整体也就是把它当作“超级源点”那么它就是一个单源最短路问题。 这个题很明显我们可以使用BFS解决但是如果每个1的位置都用一次BFS搜索未免也太麻烦那么我们可以用多源最短路的思想把所有0当作起点然后去搜索1并填充最短路径。 那么为什么不用所有的1为起点去搜索0呢因为我们需要填写的信息是1的位置如果用1去搜索0的话最后就不能找到原来那个1的位置。
代码示例
class Solution {
public:int dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};vectorvectorint updateMatrix(vectorvectorint mat){int mmat.size(),nmat[0].size();vectorvectorint ret(m,vectorint(n,-1));//充当了哈希表的功能queuepairint,int q;for(int i0;im;i)//把所有起点加入队列中{for(int j0;jn;j){if(mat[i][j]0){q.push({i,j});ret[i][j]0;}}}int tmp 0;while(!q.empty()){tmp;int sz q.size();while(sz--){auto [i,j]q.front();q.pop();for(int k0;k4;k){int xdx[k]i,ydy[k]j;if(x0xmy0ynret[x][y]-1){ret[x][y]tmp;q.push({x,y});}}}}return ret;}
};
四、拓扑排序问题
在一个有向无环图中要保证在 “被指向的节点” 出现之前它的 “父节点” 要先出现。
通常用顶点来表示一个活动用边的指向来表示活动之间的先后顺序。如 如上拓扑排序的结果可能有多种只要合法就行。
排序方法
1.记录每个顶点的入度边个数和出度边的指向。2.把所有入度边为0的节顶点push到队列中。3.拿出队头元素加入到结果中。4.把该元素指向的所有顶点入度边减1并判断如果有顶点的入度边为0则push到队列。循环执行3,4部直到队列为空则完成排序。
210. 课程表 II - 力扣LeetCode class Solution {
public:vectorint findOrder(int numCourses, vectorvectorint prerequisites) {vectorint in(numCourses), ret;vectorvectorint out(numCourses);for(int i0;iprerequisites.size();i){int aprerequisites[i][0];int bprerequisites[i][1];in[a];out[b].push_back(a);} queueint q;for(int i0;inumCourses;i)if(in[i]0) q.push(i);while(!q.empty()){int v q.front();ret.push_back(v);q.pop();for(int i0;iout[v].size();i)if(--in[out[v][i]]0) q.push(out[v][i]);}if(ret.size()!numCourses) return {};return ret;}
};
