【BFS】学习
相关知识
BFS先找到的一定最短，但如果是加权的路就会出现问题，就应采用Dijkstra最短路径算法解决加权路径的最短路。
BFS可以解决：
1.从A点出发是否存在到达B的路径（DFS也可以做到
2.从A出发到达B的最短路径（如果数据小，20（数组行列数）以内，DFS也行
DFS、BFS的区别
(1条消息) 什么时候用DFS，什么时候用BFS?_dfs规模为多少时适合_yishuige的博客-CSDN博客
序号 | BFS | DFS |
1 | BFS代表宽度优先搜索 | DFS代表深度优先搜索 |
2 | BFS（宽度优先搜索）使用队列数据结构来查找最短路径 | DFS（深度优先搜索）使用栈数据结构 |
3 | BFS更适合搜索更接近给定源的顶点 | 如果有远离源的解决方案，则DFS更适合 |
4 | BFS首先考虑所有邻居，因此不适合用于游戏或拼图中的决策树。 | DFS更适用于游戏或拼图问题。我们做出决定，然后探索有关该决定的所有路径。如果这一决定带来获胜局面，我们将停止。 |
5 | 当使用邻接表时，BFS的时间复杂度为O（V+E）；当使用邻接矩阵时，BFS的时间复杂度为O（V^2），其中V表示顶点，E表示边。 | 当使用邻接表时，DFS的时间复杂度也是O（V+E），当使用邻接矩阵时，DFS的时间复杂度也是O（V^2），其中V表示顶点，E表示边。 |
实现方法 | 基本思想 | 解决问题 | N规模 | |
DFS | 栈/递归 | 回溯法，一次访问一条路，更接近人的思维方式, | 所有解问题，或连通性问题 | 不能太大,<=200 |
BFS | 队列 | 分治限界法，一次访问多条路，每一层需要存储大量信息 | 最优解问题，如最短路径 | 可以比较大，因为可以用队列解决,<=1000 |
走迷宫
题面可以看这个：(1条消息) acwing——844. 走迷宫_suxiaorui的博客-CSDN博客
#include
#include
#include
#include
using namespace std;
#define x first
#define y second
const int N=110;typedef pair PII;//存坐标
int n,m;
int g[N][N];//存地图
int dist[N][N];//存每个点到起点的距离
queue q;int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};int bfs(int x1,int y1)
{memset(dist,-1,sizeof dist);//初始化数组dist全为-1 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.x+dx[i];int b=t.y+dy[i];if(a<1||a>n||b<1||b>n) continue;if(g[a][b]!=0) continue;if(dist[a][b]>0) continue;//判断是否访问过 q.push({a,b});//压入满足条件的点 dist[a][b]=dist[t.x][t.y]+1;if(a==n&&b==m) return dist[n][m];//到达了终点，直接返回距离 }}
}
int main()
{cin>>n>>m;for(int i=1;i>g[i][j];}}int res=bfs(1,1); cout< 这里发现头文件cstring和string竟然是不一样的，memset要用ctring。
理一理思路：
先把起点放队列里，
只要队列里有数就弹出头结点，然后遍历头结点的四个方向，如果有点满足题目条件，就压入队列中；同时更新满足条件的点的dist，当点到达终点时直接退出循环，并返回dist。