BFS（广度优先搜索）——搜索算法

        BFS，也就是广度（宽度）优先搜索，二叉树的层序遍历就是一个BFS的过程。而前、中、后序遍历则是DFS（深度优先搜索）。从字面意思也很好理解，DFS就是一条路走到黑，BFS则是一层一层地展开。

关于二叉树的创建与遍历，大家可以参考下文：

二叉树创建和遍历_二叉树的建立与遍历-CSDN博客

下图分别是DFS和BFS的遍历顺序图解： 

    

一、层序遍历

接下来我们直接来看题，从题中感受BFS的魅力。

        N叉树与二叉树的区别无非就是二叉树最多只有两个子节点用left和right两个指针就够储存。而N叉树有N多个节点，需要一个指针数组来储存。

在用BFS解决问题时几乎都要借助队列结构，用队列的先进先出特性来储存上一层的数据。

        首先把根节点放到队列里面，然后从队列里面取节点出来，把节点取出来后，通过它找到它的子节点并带入到队列里面。那么这个节点的使命就算完成了，需要把它踢出队列。循环往复直到最后队列为空，则完成层序遍历。

        但对于这个题并不是简单的层序遍历就行，它还要把每一层划分出来。这个其实也很简单，只要记录每一层有几个节点（记为n个），然后一次性的遍历n个，并把这n个元素用数组储存起来。可以直接使用size()计算该层元素个数。

代码示例：

class Solution {
public:vector<vector<int>> levelOrder(Node* root){if(!root) return {};vector<vector<int>> ret;queue<Node*> qu;qu.push(root);while(!qu.empty()){vector<int> arr;int n=qu.size();//获取该层有一个元素while(n--)//取出该层的所以元素并把子节点带入{Node* rt=qu.front();qu.pop();arr.push_back(rt->val);for(int i=0;i<rt->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 k=0;k<4;k++)

        x1 = x+dx[k], y1 = y+dy[k];

就可以得到(x, y)的上下左右坐标的(x1, y1)。

        它的扩展逻辑就和上文层序遍历中那一题差不多，但需要一个变量记录层数。在扩展过程中需要判断是否是目标值，还需要把扩展到的元素做标记。

代码示例：

class Solution {
public:int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};int nearestExit(vector<vector<char>>& maze, vector<int>& entrance){int n = maze.size(),m = maze[0].size();vector<vector<bool>> hash(n,vector<bool>(m));//记录是否已经搜索过queue<pair<int,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 k=0;k<4;k++){int x = a+dx[k],y = b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&!hash[x][y]&&maze[x][y]=='.'){if(x==0||x==n-1||y==0||y==m-1) return ret;hash[x][y] = true;qu.push({x,y});}}}}return -1;}
};

        这个题我们可以做一个多趟的BFS，首先确定第一个起点和终点，进行BFS搜索并记录路径长度。

        注意：由题可知没有两棵树的高度是相同的，也就是说树的高度和它的坐标是一一对应的。

具体操作如下：

        把所有树的高度（>1的元素）都记录到一个数组中，然后对该数组进行排序。这样我们就知道搜索的先后顺序。

        封装一个bfs函数，如pair<int,int> bfs(int x,int y,int target,vector<vector<int>>& 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(vector<vector<int>>& forest){m = forest.size(),n = forest[0].size();vector<int> arr;for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(forest[i][j]>1) arr.push_back(forest[i][j]);sort(arr.begin(),arr.end());int x = 0,y = 0;for(int i=0;i<arr.size();i++){if(i==0&&arr[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;}pair<int,int> bfs(int x,int y,int target,vector<vector<int>>& forest){vector<vector<bool>> hash(m,vector<bool>(n));queue<pair<int,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 k=0;k<4;k++){int x1 = a+dx[k],y1 = b+dy[k];if(x1>=0&&x1<m&&y1>=0&&y1<n&&!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};vector<vector<int>> updateMatrix(vector<vector<int>>& mat){int m=mat.size(),n=mat[0].size();vector<vector<int>> ret(m,vector<int>(n,-1));//充当了哈希表的功能queue<pair<int,int>> q;for(int i=0;i<m;i++)//把所有起点加入队列中{for(int j=0;j<n;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 k=0;k<4;k++){int x=dx[k]+i,y=dy[k]+j;if(x>=0&&x<m&&y>=0&&y<n&&ret[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:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> in(numCourses), ret;vector<vector<int>> out(numCourses);for(int i=0;i<prerequisites.size();i++){int a=prerequisites[i][0];int b=prerequisites[i][1];in[a]++;out[b].push_back(a);}    queue<int> q;for(int i=0;i<numCourses;i++)if(in[i]==0) q.push(i);while(!q.empty()){int v = q.front();ret.push_back(v);q.pop();for(int i=0;i<out[v].size();i++)if(--in[out[v][i]]==0) q.push(out[v][i]);}if(ret.size()!=numCourses) return {};return ret;}
};