搜索与图论第二期 BFS

---

前言

BFS跟DFS同样重要，也一定要熟练的掌握！！！

一、BFS的基本内容

BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。
如果所有节点均被访问，则算法中止。
BFS同样属于盲目搜索。
一般用队列数据结构来辅助实现BFS算法。

算法步骤：

1首先将根节点放入队列中。
2从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。
3若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
重复步骤2。

模板：

 
记录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.八数码：

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十分重要希望我们都能够熟练的掌握，感谢大家的观看！！！

原文地址：https://blog.csdn.net/2301_80882026/article/details/135531066

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！