数据结构与算法学习笔记----BFS广度优先搜索
@@ author: 明月清了个风
@@ first publish time: 2024.12.6
ps⛹这两题的代码思路分别写在每一题里了。
广度优先搜索BFS
BFS（Breadth-First Search），广度优先搜索是一种图或树的搜索遍历算法，
相较于DFS而言，广搜从图的起始点开始，访问该点的邻点并以此逐步遍历所有节点，特点是按照层级遍历图和树；而深搜的特点是路径的寻找，强调点到点的概念。
由于需要遍历所有的点和边，因此一般的时间复杂度为 O ( V + E ) O(V + E) O(V+E),V表示节点数量，E表示边数。
一般在题目中通过维护一个队列进行搜索，代码框架如下
void bfs()
{
queue<> q; // 创建一个队列
while(q.size())
{
auto t = q.front(); 取出队头
q.pop();
for(;;) // 遍历t的邻点， 并更新相关量
{
if() // 判断点的合法性
}
}
}
其他的具体看题目吧，每道题的搜索过程中需要维护的东西都不太一样，也会涉及到具体的变动，个人觉得DFS和BFS大多数时候只是一种思想。
Acwing 844. 走迷宫
[原题链接](844. 走迷宫 - AcWing题库)
给定一个 n × m n \times m n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0 0 0或者 1 1 1，其中 0 0 0表示可以走的路， 1 1 1表示不能通过的墙壁。
最初，有一个人位于左上角 ( 1 , 1 ) (1,1) (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 ( n , m ) (n,m) (n,m)处，至少需要移动多少次。
数据保证 ( 1 , 1 ) (1,1) (1,1)处和 ( n , m ) (n,m) (n,m)处的数字为 0 0 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n n n和 m m m。
接下来 n n n行，每行包含 m m m个整数（ 0 0 0或 1 1 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动到右下角的最少移动次数。
数据范围
1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1≤n,m≤100
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N];
int dist[N][N];
int n, m;
int bfs()
{
queue<PII> q; // 创建一个队列，队列中存的是遍历到的点的坐标
memset(dist, -1, sizeof dist); // 初始化所有点的距离为-1
dist[0][0] = 0; // 起点距离为0
q.push({0, 0}); // 起点入队
while(q.size()) // 只要队列中有点
{
auto t = q.front(); // 取出队头
q.pop();
int x = t.first, y = t.second; // 取出当前点的坐标
// 上下左右四个点的偏移量
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for(int i = 0; i < 4; i ++) //分别判断上下左右四种走法
{
int a = x + dx[i], b = y + dy[i]; // 计算走到的点的坐标
if(a < 0 || b < 0 || a >= n || b >= m) continue; // 坐标合法性判断
if(g[x][y]) continue; // 判断能不能走，也就是是不是1
if(dist[a][b] != -1) continue; // 判断有没有走到过这点了，在这之前走到过肯定更近就不用更新了。
dist[a][b] = dist[x][y] + 1; // 更新这点的距离
q.push({a, b}); // 新点入队
}
}
return dist[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
cin >> g[i][j];
}
cout << bfs() << endl;
return 0;
}
Acwing 845. 八数码
[原题链接](845. 八数码 - AcWing题库)
在一个 3 × 3 3 \times 3 3×3的网格中， 1 ∼ 8 1 \sim 8 1∼8这 8 8 8个数字和一个x恰好不重不漏地分布在这 3 × 3 3 \times 3 3×3的网格中。
例如:
1 2 3
x 4 6
7 5 8
在游戏过程中，可以把x与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 3×3 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1。
思路
这题虽然给的是一个矩阵的变形，但是不管是在对比还是处理的时候都要转换成字符串进行，因此，不如直接使用字符串进行操作。
其次，和上一次一样，我们需要记录到达每一个状态用到的步数，上一题中因为是坐标可以直接用数组存，而这一题其实是(string, int)的键值对，因此采用哈希表存，也就是stl中的unordered_map
第二个注意点就是状态的转换。队列中存的是字符串，但是在转换时需要按照矩阵的坐标进行，因此要找到在x在字符串中的坐标int k = t.find('x')（find返回的x在字符串中的下标），然后通过int a = k / 3, b = k % 3还原出其在矩阵中的坐标，至于状态转换就和上一题一样使用偏移量矩阵了。
其他的注意点写在注释里了
代码
#include <iostream>
#include <unordered_map>
#include <queue>
#include <cstring>
using namespace std;
int bfs(string st)
{
string ed = "12345678x"; // 最终需要到达的状态
unordered_map<string, int> d; // 相当于上一题的d数组，记录每一步的距离
queue<string> q; // 队列存的是每一种可以到的状态
q.push(st); // 起始点入队
d[st] = 0; // 到达起点的步数为0
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 偏移量矩阵
while(q.size())
{
auto t = q.front(); // 取出队头
q.pop();
if(t == ed) return d[t]; // 如果是最后结果，直接返回
int dist = d[t]; // 记录到当前点的距离
int k = t.find('x'); // 找到在当前状态中的下标
int a = k / 3, b = k % 3; // 还原成矩阵中的坐标
for(int i = 0; i < 4; i ++) // 状态转移，向四个方向走
{
int x = a + dx[i], y = b + dy[i]; // 走到的坐标
if(x < 0 || y < 0 || x >= 3 || y >= 3) continue; // 合法性判断
swap(t[x * 3 + y], t[k]); // 合法，就走过去，相当于x在字符串中的位置交换
if(!d.count(t)) // 看这种状态有没有走过
{
d[t] = dist + 1; // 没走过就更新入队
q.push(t);
}
swap(t[x * 3 + y], t[k]); // 一定要还原，因为这是在循环中。
}
}
return -1;
}
int main()
{
char a;
string start;
for(int i = 0; i < 9; i ++)
{
cin >> a;
start += a;
}
cout << bfs(start) << endl;
return 0;
}