dfs利用的是栈,bfs利用的是队列
如同y总所说的,不需要理解如何用队列实现一个bfs
而是跟着y总,告诉我们怎么做,然后我们自己判断一下这种是不是bfs
如图:取出的顺序和加入的顺序实际上都是bfs的顺序
一般的bfs框架形式如图:
由于bfs的层次遍历原理,它会优先遍历距离最短的点,因此相比dfs,它可以做到找最小步数的功能,或者说,最短路径
如图,右边的绿色数字即距离起点的距离大小(树的层数),由于从最短距离开始遍历,一直递增距离大小,可以找到最短的路径到达终点
并且由于判重数组的存在,bfs可以搜索含环的图
写一道模板题:https://www.acwing.com/problem/content/description/1103/
bfs写法:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define x first
#define y second
using namespace std;
const int N = 210;
typedef pair<int, int> PII;
int n, m;
char g[N][N];
int dist[N][N]; // 把判重和距离数组合为一个
int bfs(PII start, PII end) // 注意 start end都是PII类型的 别写错了
{
queue<PII> q;
memset(dist, -1, sizeof dist); // 把距离数组都初始化成-1,-1表示无法达到
dist[start.x][start.y] = 0; // 起点开始,距离为0
q.push(start); // 将起点入队
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//上下左右的偏移量
while(q.size())
{
PII t = q.front();
q.pop();
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue; // 出界
if (dist[a][b] != -1) continue; // 重复
if (g[a][b] == '#') continue; // 障碍物
dist[a][b] = dist[t.x][t.y] + 1;//满足条件能走,距离+1;
if (end == make_pair(a, b)) return dist[a][b]; // 到终点了
q.push({a, b});
}
}
return -1;//无法达到
}
int main()
{
int T;
cin >> T;
while(T --)
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
PII start, end;
for (int i = 0; i < n; i ++ )//寻找起点和终点
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'S') start = {i, j};
else if (g[i][j] == 'E') end = {i, j};
int distance = bfs(start, end);
if (distance == -1) printf("oop!\n");
else printf("%d\n", distance);
}
return 0;
}
原文地址:http://www.cnblogs.com/lxl-233/p/16818418.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性