新型网络搜索引擎,网站 优化 分析,html5响应式网站源码,兰州网络优化前言
BFS跟DFS同样重要#xff0c;也一定要熟练的掌握#xff01;#xff01;#xff01;
一、BFS的基本内容
BFS是从根节点开始#xff0c;沿着树(图)的宽度遍历树(图)的节点。 如果所有节点均被访问#xff0c;则算法中止。 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 {按照题目要求生成下一步节点nextif (判断 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;//终点queuestringq;//宽搜队列unordered_mapstring, intd;//距离数组,到开始的距离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*3bswap(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十分重要希望我们都能够熟练的掌握感谢大家的观看
