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