广度优先搜索 Breadth-First-Search
广度优先搜索（Breadth First Search，BFS），简称广搜，又称宽度优先搜索。它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则拓展第二层结点。如此依次拓展，检查下去，直至发现目标结点为止。如果拓展完所有结点，都没有发现目标结点，则问题无解。
广度优先遍历类似于层次遍历。其特点是尽可能先对横向进行搜索, 从出发点开始, 按照该点的路径长度由短到长的顺序访问图中各顶点。
基本步骤演示
（1）给出一连通图，如图，初始化全是白色（未访问）；
（2）搜索起点V1（灰色）；
（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；
（4）对V2，V3，V4重复以上操作；
（5）直到终点V7被染灰，终止；
（6）最短路径为V1，V4，V7.
例题 1 洛谷P1443 马的遍历
题目描述
有一个 n*m 的棋盘 (1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入格式
一行四个数据，棋盘的大小和马的坐标
输出格式
一个 n*m 的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
输入输出样例
- 输入
3 3 1 1
- 输出
0 3 2
3 -1 1
2 1 4分析
好像可以深搜啊, 但是深搜的问题是如果没有遍历完所有的结点, 是没办法确定最少步数的. 400的规模, 极端情况下, 每个点都走过, 然后到达终点, 可能的深度是 400 * 400 = 160000. 暴栈是一定的.
有没有办法, 走到这个点了, 就能确定最少步数嘛?
可以采用广搜的方式, 走第一步能到第一层, 走第二步, 能到第二层. 这就是层次遍历. 我们可以用个数组保存每层的坐标.
保存坐标有两个方法:
- x数组 y数组
- x, y 组成一个结构体.
把每层的节点放入数组里, 第i层的开始下标和结束下标我们需要用两个变量 head 和 tail 来记录.
参考代码
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int x, y;//一个结构体，x，y是队列该位置放的点的x，y值
} q[160010];//这里一定要注意数组大小
int head = 0, tail = 1;
int chess[401][401], n, m, sx, sy;
int dir[8][2] = {
{-1, -2}, {-1, 2},
{-2, -1}, {-2, 1},
{1, -2}, {1, 2},
{2, -1}, {2, 1},
};
void bfs(int x, int y)
{
chess[sx][sy] = 0;//第一个点入队
q[1].x = x;
q[1].y = y;
while(head < tail)
{
head++;//头指针加 1
int step = chess[q[head].x][q[head].y] + 1;//这个s是指扩展到新点时所需要的最少步数，就是上一个点的步数加1
for(int i=0;i<8;++i)
{
int nx = q[head].x + dir[i][0];
int ny = q[head].y + dir[i][1];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
chess[nx][ny]==-1)//没有超出棋盘并且没有走过
{
tail++;
q[tail].x = nx;
q[tail].y = ny;//新点入队
chess[nx][ny] = step; //标记到达该点的最小步数
}
}
}
}
int main()
{
cin>> n >> m >> sx >> sy;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
chess[i][j] = -1;//初始化
bfs(sx, sy);
for(int i=1;i<=n; i++)
{
for(int j=1;j<=m;++j)
printf("%-5d", chess[i][j]);//输出，注意格式
printf("\n");
}
return 0;
}head 和 tail 以及层次数组其实就是个队列.
我们可以使用STL的queue来实现.
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int chess[406][406];
int dir[8][2] = {
{-1, -2}, {-1, 2},
{-2, -1}, {-2, 1},
{1, -2}, {1, 2},
{2, -1}, {2, 1},
};
int n, m;
void bfs(int x, int y)
{
queue<int> qx;
queue<int> qy;
int cnt, next_cnt;
int step, i, j;
qx.push(x);
qy.push(y);
next_cnt = 1;
step = 0;
chess[x][y] = step;
while(next_cnt) {
cnt = next_cnt;
next_cnt = 0;
// printf("queue count:%d\n", cnt);
step++;
for(i = 1; i <= cnt; i++) {
x = qx.front();
y = qy.front();
qx.pop();
qy.pop();
for(j = 0; j < 8; j++) {
int tx = x + dir[j][0];
int ty = y + dir[j][1];
if(tx < 1 || ty < 1)
continue;
if(tx > n || ty > m)
continue;
if(chess[tx][ty] == -1) {
chess[tx][ty] = step;
qx.push(tx);
qy.push(ty);
next_cnt++;
}
}
}
}
}
int main()
{
int x, y, i, j;
scanf("%d %d %d %d", &n, &m, &x, &y);
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
chess[i][j] = -1;
}
}
bfs(x, y);
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
printf("%-5d", chess[i][j]);
}
printf("\n");
}
return 0;
}bfs框架
通过上面例题, 总结出 bfs 框架
粗略版本:
void BFS()
{ … … //初始化起点入队
while(!q.empty()) //判断队是否为空
{ … … //获取队首元素
if(... …){… …} //判断是否是终点
for(int i=0;i<4;i++) //四个方向
{
k.x=p.x+dir[i][0];
k.y=p.y+dir[i][1];
//向各个方向走一步
if(judge()) //判断能不能走
{
… … //各种处理
vis[k.x][k.y]=1; //标记
q.push(k); //入队
}
}
}
}详细版本:
const int N = 1000;
bool vis[N][N]; //记录访问数组
struct Node {
int x;
int y;
};
Node bfs(int sx, int sy) //返回终点
{
queue <Node> q;
Node cur, next;
cur.x = sx;
cur.y = sy;//初始结点信息
q.push(cur);//初始结点入队，
while (!q.empty()) //开启bfs过程
{
cur = q.front();//取队头结点
q.pop();
if (cur.x == 终点.x && cur.y == 终点.y) return cur;//过程结束条件
int i, nx, ny;//新的待遍历结点
for (i = 0; i < 4; i++) {
nx = cur.x + dx[i];
ny = cur.y + dy[i];
if (judge(nx, ny))continue; //不可以走，边界或者已遍历等
next = cur;
next.x = nx;
next.y = ny;
q.push(next);//新结点入队
}
}
}
dfs 和 bfs 的比较
我们假设一个节点衍生出来的相邻节点平均的个数是N个，那么当起点开始搜索的时候，队列有一个节点，当起点拿出来后，把它相邻的节点放进去，那么队列就有N个节点，当下一层的搜索中再加入元素到队列的时候，节点数达到了，那么，一旦N是一个比较大的数的时候，这个树的层次又比较深，那这个队列就得需要很大的内存空间了。
于是广度优先搜索的缺点出来了：在树的层次较深 子节点数较多的情况下，消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多，并且树的层次不会太深的情况。
那么深度优先就可以克服这个缺点，因为每次搜的过程，每一层只需维护一个节点。但回过头想想，广度优先能够找到最短路径，那深度优先能否找到呢？深度优先的方法是一条路走到黑，那显然无法知道这条路是不是最短的，所以你还得继续走别的路去判断是否是最短路？
于是深度优先搜索的缺点也出来了：难以寻找最优解，仅仅只能寻找有解。其优点就是内存消耗小，克服了刚刚说的广度优先搜索的缺点。
| | 实现方法 | 基本思想 | 解决问题 | N规模 |
|---|---|---|---|---|
| DFS | 栈/递归 | 回溯法，一次访问一条路，更接近人的思维方式. | 所有解问题，或连通性问题 | 不能太大, <=200 |
| BFS | 队列 | 分治限界法，一次访问多条路，每一层需要存储大量信息 | 最优解问题，如最短路径 | 可以比较大，因为可以用队列解决,<=1000 |
例题 2 洛谷P1825 [USACO11OPEN]Corn Maze S
题目描述
去年秋天，奶牛们去参观了一个玉米迷宫，迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用：一头奶牛可以从这个装置的起点立即到此装置的终点，同时也可以从终点出发，到达这个装置的起点。如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。
玉米迷宫的外部完全被玉米田包围，除了唯一的一个出口。
这个迷宫可以表示为N×M的矩阵(2 ≤ N ≤ 300; 2 ≤ M ≤ 300)，矩阵中的每个元素都由以下项目中的一项组成：
玉米，这些格子是不可以通过的。
草地，可以简单的通过。
一个装置的结点，可以将一头奶牛传送到相对应的另一个结点。
出口
奶牛仅可以在相邻两个格子之间移动，要在这两个格子不是由玉米组成的前提下才可以移动。奶牛能在一格草地上可能存在的四个相邻的格子移动。从草地移动到相邻的一个格子需要花费一个单位的时间，从装置的一个结点到另一个结点需要花费0个单位时间。
被填充为玉米的格子用“#”表示，草地用“.”表示，每一对装置的结点由相同的大写字母组成“A-Z”，且没有两个不同装置的结点用同一个字母表示，出口用“=”表示。
Bessie在这个迷宫中迷路了，她知道她在矩阵中的位置，将Bessie所在的那一块草地用“@”表示。求出Bessie需要移动到出口处的最短时间。
例如以下矩阵，N=5，M=6：
###=##
#.W.##
#.####
#.@W##
######唯一的一个装置的结点用大写字母W表示。
最优方案为：先向右走到装置的结点，花费一个单位时间，再到装置的另一个结点上，花费0个单位时间，然后再向右走一个，再向上走一个，到达出口处，总共花费了3个单位时间。
输入格式
第一行：两个用空格隔开的整数N和M；
第2-N+1行：第i+1行描述了迷宫中的第i行的情况（共有M个字符，每个字符中间没有空格。）
输出格式
一个整数，表示Bessie到达终点所需的最短时间。
输入输出样例
- 输入 #1复制
5 6
###=##
#.W.##
#.####
#.@W##
######- 输出 #1复制
3
分析
数据规模 300, 求最短时间, 所以是广搜. 深搜的话, 要遍历所有可能的路径, 然后求得最短时间, 我加了剪枝也只得了73分, 而且会MLE, 递归太深, 爆栈了.
一个难点是传送点的处理.
dfs参考代码(73分)
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 303;
const int LIMIT = 0x7f7f7f7f;
int m, n, ans = LIMIT;
char a[MAXN][MAXN];
int f[MAXN][MAXN];
int x, y;
struct Node
{
int x, y;
int to;
};
Node node[30 * 2 + 6];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void dfs(int x, int y, int t)
{
if (t >= ans)
return;
if (f[x][y] <= t)
return;
if (a[x][y] == '=')
{
ans = min(ans, t);
return;
}
if (a[x][y] == '#')
return;
if (a[x][y] == '.')
{
f[x][y] = t;
}
if (a[x][y] >= 'A' && a[x][y] <= 'Z')
{
int idx = a[x][y] - 'A';
if (node[idx].x == x && node[idx].y == y)
{
idx += 30;
}
x = node[idx].x;
y = node[idx].y;
}
for (int i = 0; i < 4; i++)
{
dfs(x + dir[i][0], y + dir[i][1], t + 1);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> &a[i][1];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = LIMIT;
if (a[i][j] == '#' || a[i][j] == '.')
continue;
if (a[i][j] >= 'A' && a[i][j] <= 'Z')
{
int idx = a[i][j] - 'A';
if (node[idx].x == 0 && node[idx].y == 0)
{
node[idx].x = i;
node[idx].y = j;
}
else
{
idx += 30;
node[idx].x = i;
node[idx].y = j;
}
continue;
}
if (a[i][j] == '@')
{
x = i;
y = j;
f[i][j] = 1;
continue;
}
}
dfs(x, y, 0);
cout << ans;
return 0;
}
bfs参考代码
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 303;
int m, n;
char a[MAXN][MAXN];
int vis[MAXN][MAXN];
int sx, sy;
struct Node
{
int x, y;
int t;
};
Node node[30 * 2 + 6];
queue<Node> q;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int bfs()
{
Node p;
p.x = sx;
p.y = sy;
p.t = 0;
q.push(p);
while (!q.empty())
{
p = q.front();
q.pop();
int x = p.x;
int y = p.y;
int t = p.t;
if (a[x][y] == '=')
{
return t;
}
if (a[x][y] >= 'A' && a[x][y] <= 'Z')
{
int idx = a[x][y] - 'A';
if (node[idx].x == x && node[idx].y == y)
{
idx += 30;
}
x = node[idx].x;
y = node[idx].y;
}
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (vis[nx][ny] == 0)
continue;
vis[nx][ny] = 0;
p.x = nx;
p.y = ny;
p.t = t + 1;
q.push(p);
}
}
return 0;
}
int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> &a[i][1];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (a[i][j] == '#')
{
continue;
}
vis[i][j] = 1;
if (a[i][j] >= 'A' && a[i][j] <= 'Z')
{
int idx = a[i][j] - 'A';
if (node[idx].x == 0 && node[idx].y == 0)
{
node[idx].x = i;
node[idx].y = j;
}
else
{
idx += 30;
node[idx].x = i;
node[idx].y = j;
}
continue;
}
if (a[i][j] == '@')
{
sx = i;
sy = j;
}
}
cout << bfs();
return 0;
}