广度优先搜索bfs

一、queue队列

1、概述

队列（queue）：是一种运算受限制的线性表。其限制只允许从表的队首进行删除操作，而在表的队尾进行插入操作。特点：先进先出

队列的插入操作又叫入队，队列的删除操作又叫出队。

2、构造

使用queue需要引入<queue>头文件、std命名空间

泛型T是我们数组要储存的数据类型，可以是 int、float、double、或者结构体等。

初始的时候queue是空的。

#include "queue"
using namespace std;
int main() {
    queue<int> q;
    return 0;
}

3、使用

1）入队与出队

push()：入队

pop()：出队

2）获取队首元素

front()：获取队首元素

3）判空

empty()：判断是否为空

4）清空

清空一个队列，需要手动清空。

while(!q.empty()) {
    q.pop();
}

2、广度优先搜索bfs

1、概述

广度优先搜索bfs：与深度优先搜索不同的是，广度优先搜索会先将与起始点距离较近的点搜索完毕，再继续搜索较远的点，而深搜却是沿着一个分支搜到最后。

bfs 从起点开始，优先搜索离起点最近的点，然后由这个最近的点扩展其他稍近的点，这样一层一层的扩展。

2、步骤

bfs需要借助队列来实现

1. 初始的时候把起始点放到队列中，并标记起点访问。
2. 如果队列不为空，从队列中取出一个元素x，否则算法结束。
3. 访问和x相连的所有点v，如果v没有被访问，把v入队，并标记已经访问
4. 重复执行步骤2。

void bfs(起始点) {
	将起始点放入队列中；
	标记起点访问；
	while(如果队列不为空) {
		访问队首元素x；
		删除队首元素；
		for(x的相邻点v) {
			if(v没被标记) {
				v加入队尾并标记；
			}
		}
	}
	队列为空，广搜结束；
}

3、迷宫问题bfs

用dfs 求解迷宫最短路有一个很大的缺点，需要枚举所有可能的路径，读入的地图一旦很大，可能的搜索方案数量会非常多，用dfs搜索显然效率会很低。

借助 bfs 来求解迷宫游戏。由于bfs是分层搜索，因此，第一次搜索到终点的时候，当前搜索的层数就是最短路径的长度。

样例

5 6 
....S*
.**...
.*..*.
*..**.
.T....

输出：7

代码

/**
 * bfs迷宫问题
 * @author  王铭颢
 * @Date  2022/11/26 15:02
 */

#include "iostream"
#include "queue"

using namespace std;

struct Node {
    int x, y, d;

    Node(int xx, int yy, int dd) {
        x = xx, y = yy, d = dd;
    }
};

int n, m;
string mp[110];
const int dir[4][2] = {{1,  0},
                       {-1, 0},
                       {0,  -1},
                       {0,  1}};
bool vst[110][110];

bool in(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

int bfs(int x, int y) {
    queue<Node> q;
    q.push(Node(x, y, 0));
    while (!q.empty()) {
        Node node = q.front();
        q.pop();
        if (!in(node.x, node.y)) continue;
        else {
            vst[node.x][node.y] = true;
            if (mp[node.x][node.y] == 'T') {
                return node.d;
            }
            if (mp[node.x][node.y] != '*') {
                for (int i = 0; i < 4; i++) {
                    if (!vst[node.x + dir[i][0]][node.y + dir[i][1]])
                        q.push(Node(node.x + dir[i][0], node.y + dir[i][1], node.d + 1));
                }
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    int x, y;
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == 'S') {
                x = i, y = j;
            }
        }
    }
    cout << bfs(x, y) << endl;
    return 0;
}