前言
BFS跟DFS同样重要,也一定要熟练的掌握!!!
一、BFS的基本内容
BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。
如果所有节点均被访问,则算法中止。
BFS同样属于盲目搜索。
一般用队列数据结构来辅助实现BFS算法。
算法步骤:
1首先将根节点放入队列中。
2从队列中取出第一个节点,并检验它是否为目标。如果找到目标,则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。
3若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
重复步骤2。文章来源:https://www.toymoban.com/news/detail-810992.html
模板:
记录head节点为已经访问;
q.push(head);
while (q.empty()) { //当队列q不为空,则继续遍历
xxx tmp = q.front(); //取出队列q的首数据
q.pop();
//判断 tmp 节点是否为终点
if (tmp为目标状态) {
输出记录,结束遍历
} else {
按照题目要求,生成下一步节点next
if (判断 next 的合法性) {
记录next节点为已经访问;
q.push(next);//将合法节点推入到队列中
}
}
}
二、典型例题
1.八数码:
文章来源地址https://www.toymoban.com/news/detail-810992.html
AC代码:
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>//哈希表存所有距离
#include <cstring>
using namespace std;
int bfs(string start) {
string end = "12345678x";//终点
queue<string>q;//宽搜队列
unordered_map<string, int>d;//距离数组,到开始的距离
q.push(start);//先把start放队列里去
d[start] = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//上下左右四个数相对于x的位置
while (q.size()) {//宽搜过程
auto t = q.front();
q.pop();
int distance = d[t];
if (t == end)//t是终点
return distance;//返回距离
//状态转移
int k = t.find('x');//k来存储x的位置,find返回x的下标
int x = k / 3, y = k % 3; //把一维数组的下标转化成二维数组的下标
for (int i = 0; i < 4; i++) {
//x,y是当前'x'的位置,a,b是移动一次之后'x'的位置
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3) {//a,b都没有出界
//二维数组的下标a,b对应到一维数组的下标a*3+b
swap(t[k], t[a * 3 + b]);//状态更新
//如果更新完之后的t之前没有搜过的话,就说明找到了一个新的状态
if (!d.count(t)) {
d[t] = distance + 1;//新的状态的距离更新
q.push(t);//把新的状态加到队列里
}
swap(t[k], t[a * 3 + b]);//恢复状态
}
}
}
return -1;//如果在宽搜的过程中没有找到,终点返回-1
}
int main() {
string start;//start存初始状态
for (int i = 0; i < 9; i++) {
char c;
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}
总结
BFS十分重要希望我们都能够熟练的掌握,感谢大家的观看!!!
到了这里,关于搜索与图论第二期 BFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!