广度优先搜索(BFS)
dongjiayu_ · · 算法·理论
引言：
BFS，全名为广度优先搜索(Breadth-First Search)，是一种用于图或树的遍历或搜索的算法。它的主要思想是由节点自身开始向它的邻节点新进展开搜索，因此也常被形象地称为“层序遍历”。
BFS 的基本概念
BFS的工作原理是，从开始节点开始，在访问节点的邻居节点之前，我们先访问其它节点。换句话说，我们旧基于当前层次来遍历节点，然后移至下一层再遍历节点。
BFS是以一种队列(Queue)结构的方式运行的，首先我们有一个包含开始节点的队列，然后：
-
从队列前端取出一个节点
-
为了防止重复访问，标记取出的节点
-
针对取出的节点，把尚未访问过的邻节点全部加入队列
-
重复以上步骤，直到队列为空
通过以上步骤将会发现，在访问节点的时候，首先访问的是距离开始节点最近的节点（层次最低的节点），然后层次逐渐提升，这就是 BFS 的特性。
BFS 伪代码模板
求最少步数
int bfs() {
queue<nn> q;
q.push({ax, ay, 0});
vis[ax][ay] = 1;
while (!q.empty()) {
nn u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = u.x + dx[i];
int ny = u.y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny]) {
q.push({nx, ny, u.step + 1});
vis[nx][ny] = 1;
if (nx == bx && ny == by) {
return u.step + 1;
}
}
}
}
return -1;
}打印最短路径
void bfs(node s) {
queue<node> q;
q.push(s);
vis[s.x][s.y] = true;
while (!q.empty()) {
node t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int newX = t.x + X[i];
int newY = t.y + Y[i];
if (judge(newX, newY)) {
pre[newX][newY] = t;
temp.x = newX;
temp.y = newY;
q.push(temp);
vis[newX][newY] = true;
}
}
}
}传送门
有点长，不展示
BFS 经典题型
1. 求最少步数：D1227 仙岛求药
根据广搜的特点，从起点开始，第一次搜索到点
所以可以直接从起点搜索一遍。在搜索过程中，如果当前点是终点，则直接输出从起点到当前点所用的步数。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m;
char c[50][50];
bool vis[50][50];
int ax, ay, bx, by;
struct nn {
int x, y, sp;
};
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int bfs() {
queue<nn> q;
q.push({ax, ay, 1});
vis[ax][ay] = 1;
while (!q.empty()) {
nn u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = dx[i] + u.x;
int ny = u.y + dy[i];
if (nx && ny && nx <= n && ny <= m && !vis[nx][ny]) {
q.push({nx, ny, u.sp + 1});
vis[nx][ny] = 1;
if (nx == bx && ny == by) {
return u.sp;
}
}
}
}
return -1;
}
int main() {
while (1) {
memset(vis, 0, sizeof vis);
cin >> n >> m;
if (n == 0 && m == 0) break;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c[i][j];
if (c[i][j] == '#') {
vis[i][j] = 1;
}
if (c[i][j] == '@') {
ax = i, ay = j;
}
if (c[i][j] == '*') {
bx = i, by = j;
}
}
}
cout << bfs() << endl;
}
return 0;
}2. 打印最短路径：迷宫问题
对于简单的问最短路径长度的问题。我们可以通过在表示位置的结构体中加上一个
而对于要打印路径问题，就需要额外的开一个数组来存放当前结点的前驱结点的信息。
用一个二维数组表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。数据保证有唯一解
输入：（一个5*5的数组）
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出：
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)开一个结构体数组来保存当前结点的前驱结点nn pre[_][_]。这样在每次BFS操作的时候，对于满足条件的结点，将其前驱结点保存在pre[nowX][nowY]中。最后通过递归就可以得到答案。
代码：
#include <bits/stdc++.h>
using namespace std;
const int n = 6;
int Maze[n][n];
bool vis[n][n];
struct nn {
int x, y;
} temp;
nn pre[n][n];
int X[] = {0, 0, -1, 1};
int Y[] = {-1, 1, 0, 0};
bool judge(int x, int y) {
if (x < 0 || x > 4 || y < 0 || y > 4)return false;
if (Maze[x][y] == 1) return false;
if (vis[x][y] == true) return false;
return true;
}
void BFS(nn s) {
queue<nn>q;
q.push(s);
vis[s.x][s.y] = true;
while (!q.empty()) {
nn t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int newX = t.x + X[i];
int newY = t.y + Y[i];
if (judge(newX, newY)) {
pre[newX][newY] = t;
temp.x = newX;
temp.y = newY;
q.push(temp);
vis[newX][newY] = true;
}
}
}
}
void jj(int x, int y) {
if (x == 0 && y == 0) {
printf("(%d, %d)\n", x, y);
return;
}
temp = pre[x][y];
jj(temp.x, temp.y);
printf("(%d, %d)\n", x, y);
}
int main() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
scanf("%d", &Maze[i][j]);
}
}
temp.x = temp.y = 0;
BFS(temp);
jj(4, 4);
return 0;
}3. 传送门类型：[USACO11OPEN] Corn Maze S
思路
如果将要被加入队列的位置是传送门，则将不加入传送门的起点拉入队列，而是将传送门的终点拉入队列
因为传送门可能再次使用，所以不标记传送门
代码：
#include <bits/stdc++.h>
using namespace std;
const int _ = 305;
int n, m;
int ax, ay, bx, by;
char c[_][_];
bool vis[_][_];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
struct nn {
int x, y;
int sp;
};
bool check(int x, int y) {
return x >= 1 && x <= n&&y >= 1 && y <= m&&!vis[x][y];
}
int bfs() {
queue<nn> q;
q.push(nn{ax, ay, 0});
vis[ax][ay] = 1;
while (!q.empty()) {
nn u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = u.x + dx[i];
int ny = u.y + dy[i];
if (check(nx, ny)) {
int xx = 0, yy = 0;
if (c[nx][ny] >= 'A' && c[nx][ny] <= 'Z') {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == c[nx][ny] && (i != nx || j != ny)) {
xx = i, yy = j;
}
}
}
q.push(nn{xx, yy, u.sp + 1});
} else {
q.push(nn{nx, ny, u.sp + 1});
vis[nx][ny] = 1;
}
if (nx == bx && ny == by) {
return u.sp + 1;
}
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c[i][j];
if (c[i][j] == '#') {
vis[i][j] = 1;
}
if (c[i][j] == '@') {
ax = i, ay = j;
}
if (c[i][j] == '=') {
bx = i, by = j;
}
}
}
cout << bfs();
return 0;
}