算法BFS搜爆路径问题

文章目录

前言

一  走迷宫问题 

二  为什么最先找到为最小的路径

三  为什么要使用队列

四  整体思路

总结

---

前言

由于对于搜索路径问题，我们如果用深度搜索dfs的话，时间会花费很多很多，所以我们就有了广度搜索bfs来搜索路径问题

---

深度优先和广度优先，这个概念我已经在树的章节已经讲过了 数据结构 树2-CSDN博客 可以去看看

一  走迷宫问题 

接下来我们用一个题目来讲解引入bfs

#include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<utility> using namespace std; //二元组 typedef pair<int,int> PII; const int N = 1010; int n; int map [N][N]; //地图 int dist[N][N]; //路径 queue<PII>q; int dx[]={-1,0,1, 0}; int dy[]={ 0,1,0,-1}; int bfs(int x1,int y1,int x2,int y2){ //初始化路径数组，这个直接对内存操作十分快 memset(dist, -1, sizeof(dist)); q.push({x1,y1}); dist[x1][y1]=0; while(!q.empty()){ //取走队列的头 auto t=q.front(); //记得弹出 q.pop(); for(int i=0;i<4;i++){ int a=t.first +dx[i]; int b=t.second+dy[i]; if(a<1||a>n||b<1||b>n)continue; if(map[a][b]!=0)continue; if(dist[a][b]>0)continue; q.push({a,b}); dist[a][b]=dist[t.first][t.second]+1; if(a==x2&&b==y2){ return dist[a][b]; } } } return -1; } int main(){ scanf("%d",&n); //当我们要输入为一行数字之后要拆开的话，直接用字符 for(int i=1;i<=n;i++){ char line[N]; scanf("%s",line); for(int j=1;j<=n;j++){ map[i][j]=line[j-1]-'0'; } } int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); int result = bfs(x1,y1,x2,y2); printf("%d",result); return 0; }

我们拿到这个题目的时候 我们先以dfs分析一边

我们上面有一个5*5的迷宫，我们什么时候要回溯 1   我们之前走过的路，我们不可能往回走 2   碰到障碍物1的时候就要回走 3   超出矩阵的范围的时候要回走 我们可以看到dfs处理这个问题很慢，当到了23*23的矩阵的时候，好像就存储不过来了，所以我们就要用bfs来解决 bfs就相当于是dfs的减枝，当我们判断有最小的时候，直接返回，因为是范围搜索，我们来画一个图就知道了

它是直接把这个每层逐层搜索的，也就是说这个树不是按照深度画的，而是按照层次来画的，这样我们就可以不要一直走到底来判断这个是否可以 但是bfs的时间比dfs的时间少了很多，但是bfs的空间开销比dfs的开销大了很多 但是我们择优选择选择bfs来解决 我们比赛通常内存大小为64MB，这个大小相当于大概可以开出1E6次方的int类型的数组，然后我们队列是开在堆的，这样可以避免爆栈

二  为什么最先找到为最小的路径

对于所有边长度相同的情况，比如地图的模型，bf3第一次遇到目标点，此时就定是从根节点到目标节点最短的路径(因为每一次所有点都是向外扩张一步，你先遇到，那你就一定最短)。bfs先找到的一定是最短的。

但是如果是加权边的话这样就会出问题了，bfs传回的是经过边数最少的解，但是因为加权了，这个解到根节点的距离不一定最短。比如1000+1000是只有两段，1+1+1+1有4段，由于bfs返回的经过边数最少的解，这里会返回总长度2000的那个解，显然不是距离最短的路径。此时我们就应该采用Diikstra最短路算法解决加权路径的最短路了

加权路径要使用Diikstra最短路算法解决

三  为什么要使用队列

 为什么需要队列? 正如以上所说，我们需要一层一层去遍历到所有结点,那么相邻结点的访问顺序如何确定?

因此我们就需要一个数据结构去存储和操作,需要使得先遍历到的结点先被存储,直到当前层都被存储之后,按照存储的先后顺序,先被存储的结点也会被先取出来继续遍历他的子节点--->综上所述，需要一种特点为先进先出的数据结构也就是队列! Queue! queue的特点是: 先进先出(first in first out --- IFO) 我们不难发现，这个深度搜索，这个是节点挨着节点，然后我们把节点放入之后，就可以根据这个节点找到下一个节点，但是深度搜索顺序是由你规定的，然后我们如果想从左到右搜索，我们就直接放入，因为队列本来就是按照顺序的，我们只要用队列头的来把子节点放入

四  整体思路

其思路为从图上一个节点出发，访问先访问其直接相连的子节点，若子节点不符合，再问其子节点的子节点，按级别顺序(一层一层)依次访问，直到访问到目标节点。 起始:将起点(源点，树的根节点)放入队列中 扩散:从队列中取出队头的结点，将它的相邻结点放入队列，不断重复这一步 终止:当队列为空时，说明我们遍历了所有的结点，整个图都被搜索了一遍

---

总结

我们当遇到 一个点是否可以到达另外一个点 到达那个点最小的步数是多少的时候 我们直接考虑使用bfs来解决 bfs最核心的就是坐标的确定和队列使用