什么是广度优先搜索？
广度优先搜索简称BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表） -- 百度百科
通俗来说，这是一种的搜索算法，特点是从一个节点开始向与这个节点连接的其他节点搜索，一层一层的搜索，直到没有点可以搜索。 从下面的图来讲，广度优先搜索是按照这样的顺序来搜索这张图的：
从1点开始搜索，搜索的顺序为 1、 2、 3、 4、 5、 6、 7。 由浅到深一层一层搜索。
广度优先搜索的详细搜索顺序
以刚才的图为例，详细看广度优先搜索的搜索过程，将已经搜索到的点涂色为绿色， 没有搜索到的点涂色为蓝色 首先从1点开始搜索
此时已经查找到1节点，直接连接的没有被搜索到的节点有2， 3
接下来查找2， 3节点
此时已经查找到2，3节点，直接连接的没有被搜索到的节点有4， 5， 6
接下来查找4， 5 ，6节点
此时已经查找到4， 5， 6结点，直接连接的没有被搜索到的节点有7
最后查找7搜索结束
可以看到广度优先搜索是一层一层搜索的搜索策略
代码实现刚才的搜索
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool vis[105];
//vis[i] = true 表示 i 点搜索过
//vis[i] = false 表示 i 点搜索过
vector <int> mp[10];
queue <int> q;
//使用一种先入先出的数据结构 queue 来实现
void bfs() {
while(!q.empty()) {
int NowPos = q.front();
//打印搜索到的点
cout << NowPos << endl;
q.pop();
//已经搜索到的点出队列，不重复查找
for(int i : mp[NowPos]) if(!vis[i]) q.push(i), vis[i] = true;
//对于连接的点，如果没有搜索到，那么这个点入队列，记录这个点已经搜索到
}
}
int main() {
for(int i = 1; i <= 7; i++) {
int number;
//和每个点相连的有多少边
cin >> number;
for(int j = 1; j <= number; j++) {
int Pos;
//每个边相连的点的编号
cin >> Pos;
mp[i].push_back(Pos);
}
}
//初始点1点入队列
//标记点1已经搜索过
q.push(1);
vis[1] = true;
bfs();
return 0;
}
广度优先搜索常用的场景
场景一 抓牛问题
抓住奶牛
Farmer John 已被告知一头逃亡母牛的位置，并希望立即抓住她。他从数轴上的点N (0 ≤ N ≤ 100,000) 开始，而奶牛在同一数轴上的点K (0 ≤ K ≤ 100,000) 处。Farmer John 有两种交通方式：步行和传送。
- 行走：FJ 可以在一分钟内从X点移动到X - 1 或X + 1点
- 传送：FJ 可以在一分钟内从X点移动到 2 × X点。
如果母牛不知道它的追逐，根本不动，FJ需要多长时间才能把它取回？
bfs 模拟农夫约翰的走路过程，队列中记录的状态是当前这一步能达到的位置。
代码部分
/*
5 17
4
*/
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 1000005;
//注意这里的MAXN是原来数据范围的10倍左右，因为考虑到农夫约翰是可以后退的，所以数组开大
int StartPos, EndPos;
bool vis[MAXN];
//vis[i] = false 代表 i 点没有走过
//vis[i] = true 代表 i 点已经走过
queue <int> q;
//队列中保存的当前走到的点
inline bool check(int Pos) {
return Pos >= 0 && Pos < MAXN && !vis[Pos];
}
int bfs() {
int Step = 0;
while(!q.empty()) {
int Size = q.size();
///注意这里的性质
///广搜的层序遍历特性
///每次入队列的点一定是同一层的
while(Size--) {
///直接查找同一层的所有点
///这些点可以用相同的步数到达
int NowPos = q.front();
if(NowPos == EndPos) return Step;
q.pop();
if(check(NowPos - 1)) q.push(NowPos - 1), vis[NowPos - 1] = true;
if(check(NowPos + 1)) q.push(NowPos + 1), vis[NowPos + 1] = true;
if(check(NowPos * 2)) q.push(NowPos * 2), vis[NowPos * 2] = true;
}
Step++;
}
}
int main() {
cin >> StartPos >> EndPos;
q.push(StartPos);
vis[StartPos] = true;
cout << bfs() << endl;
return 0;
}
另一种稍有不同的写法
/*
5 17
4
*/
#include <iostream>
#include <queue>
using namespace std;
typedef pair <int, int> points;
const int MAXN = 1000005;
int StartPos, EndPos;
bool vis[MAXN];
queue <points> q;
/// 用pair的second直接保存当期位置用了多少步
inline bool check(int Pos) {
return Pos >= 0 && Pos < MAXN && !vis[Pos];
}
int bfs() {
int Step = 0;
while(!q.empty()) {
int NowPos = q.front().first;
int NowStep = q.front().second;
if(NowPos == EndPos) return NowStep;
q.pop();
if(check(NowPos - 1)) q.push(make_pair(NowPos - 1, NowStep + 1)), vis[NowPos - 1] = true;
if(check(NowPos + 1)) q.push(make_pair(NowPos + 1, NowStep + 1)), vis[NowPos + 1] = true;
if(check(NowPos * 2)) q.push(make_pair(NowPos * 2, NowStep + 1)), vis[NowPos * 2] = true;
}
}
int main() {
cin >> StartPos >> EndPos;
q.push(make_pair(StartPos, 0));
/// 一开始是0步
vis[StartPos] = true;
cout << bfs() << endl;
return 0;
}
场景二 迷宫问题
判断能否从一个二维图一点到达另一个点
给出一张图，每次移动可以上下左右移动一格，其中0表示可以移动到的点， 1表示障碍， 判断能否从起点走到终点。 （保证起点终点一定是0）
起点：左上角
终点：右下角
测试样例
7 7
0 1 0 1 0 1 0
0 1 0 0 0 1 0
0 0 1 1 0 0 0
0 0 0 0 0 1 0
0 0 1 0 1 0 0
0 1 0 1 0 0 0
1 0 1 0 0 1 0
true
7 7
0 1 0 1 0 1 0
0 1 0 0 0 1 0
0 0 1 1 0 0 0
0 0 0 0 0 1 0
0 0 1 0 1 0 1
0 1 0 1 0 0 0
1 0 1 0 0 1 0
false
这样的题目显然也可以用dfs解决， 本次使用bfs解法
队列中保存二维点的坐标，用dir数组中的值和队列中的点的坐标加减，模拟上下左右移动，结束的条件是队列中入队了目标点或者队列为空。
#include <iostream>
#include <queue>
using namespace std;
typedef pair <int, int> points;
queue <points> q;
///队列中保存二维点的坐标
int n, m, mp[10][10];
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
///dir数组用于模拟移动的过程
bool vis[10][10];
/// vis[i] = true 表示当前点已经走过
/// vis[i] = false 表示当前点没有走过
inline bool check(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
/// 判断点 x, y 有没有越界
}
bool bfs() {
while(!q.empty()) {
points NowPos = q.front();
if(NowPos.first == n && NowPos.second == m) return true;
///如果搜索到目标点那么结束bfs
q.pop();
for(int i = 0; i < 4; i++) {
int x = NowPos.first + dir[i][0];
int y = NowPos.second + dir[i][1];
if(check(x, y) && !vis[x][y] && !mp[x][y]) {
///一个点可以移动到的条件
//1、这个点不越界
//2、这个点没有已经走过
//3、这个点是可以到达的
vis[x][y] = true;
q.push(make_pair(x, y));
}
}
}
return false;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> mp[i][j];
q.push(make_pair(1, 1));
vis[1][1] = true;
//起点直接入队列标记已经走过
if(bfs()) cout << "true" << endl;
else cout << "false" << endl;
return 0;
}
计算从二维图一点到达另一个点需要多少步
一点小区别 bfs 时利用 bfs 层序遍历特性每次只计算一层，每一层的步数相同
#include <iostream>
#include <queue>
using namespace std;
typedef pair <int, int> points;
queue <points> q;
/// 队列中保存的是当前点的坐标
/// 注意这里也可选择直接将当前位置移动多少步入队列
/// 那么此时这个队列中应该保存点的坐标和移动步数
/// 可是考虑用下面的结构体来保存
/**
struct Q {
int x, y, Step;
};
queue <Q> q;
**/
int n, m, mp[10][10];
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
bool vis[10][10];
inline bool check(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int bfs() {
int Step = 0;
while(!q.empty()) {
int Size = q.size();
//每一层的步数相同
while(Size--) {
points NowPos = q.front();
if(NowPos.first == n && NowPos.second == m) return Step;
q.pop();
for(int i = 0; i < 4; i++) {
int x = NowPos.first + dir[i][0];
int y = NowPos.second + dir[i][1];
if(check(x, y) && !vis[x][y] && !mp[x][y]) {
vis[x][y] = true;
q.push(make_pair(x, y));
}
}
}
Step++;
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> mp[i][j];
q.push(make_pair(1, 1));
vis[1][1] = true;
cout << bfs() << endl;
return 0;
}
/*
7 7
0 1 0 1 0 1 0
0 1 0 0 0 1 0
0 0 1 1 0 0 0
0 0 0 0 0 1 0
0 0 1 0 1 0 0
0 1 0 1 0 0 0
1 0 1 0 0 1 0
14
*/
改变dir数组的值改变移动规则
题目 ： HDU 1372
/**
Knight Moves
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10397 Accepted Submission(s): 6119
Problem Description
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to
find the shortest closed tour of knight moves that visits each square of a given set of n
squares on a chessboard exactly once. He thinks that the most difficult part of the problem
is determining the smallest number of knight moves between two given squares and that, once
you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves
the "difficult" part.
Your job is to write a program that takes two squares a and b as input and then determines
the number of knight moves on a shortest route from a to b.
Input
The input file will contain one or more test cases. Each test case consists of one line
containing two squares separated by one space. A square is a string consisting of a letter
(a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output
For each test case, print one line saying "To get from xx to yy takes n knight moves.".
Sample Input
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
**/
题目大意:
在一个8 * 8的棋盘中，国际象棋中骑士最少多少步能从一个点移动到另一个点。
骑士是国际象棋中的棋子，类似于中国象棋中的马，有八种走法：
一 左走一格向前走两格，二 左走一格向后走两格，
三 左走两格向前走一格，四 左走两格向后走一格，
五 右走一格向前走两格，六 右走一格向后走两格，
七 右走两格向前走一格，八 右走两格向后走一格。
可以越子，没有"中国象棋"中"蹩马腿"的限制。也是走“日”字格，是三乘二的“日”字格。骑士的价值为3，虽然价值不高，却灵活，易调动，易双抽，从这一点看，它的价值不亚于后。
---- 百度百科
一点小区别：dir数组变化
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair <int, int> points;
queue <points> q;
/// 队列中保存的是当前点的坐标
/// 注意这里也可选择直接将当前位置移动多少步入队列
/// 那么此时这个队列中应该保存点的坐标和移动步数
/// 可是考虑用下面的结构体来保存
/**
struct Q {
int x, y, Step;
};
queue <Q> q;
**/
int n, m;
int dir[8][2] = {2, 1, 2, -1, 1, 2, 1, -2, -1, 2, -1, -2, -2, 1, -2, -1};
bool vis[10][10];
inline bool check(int x, int y) {
return x >= 1 && x <= 8 && y >= 1 && y <= 8;
}
int bfs() {
int Step = 0;
while(!q.empty()) {
int Size = q.size();
//每一层的步数相同
while(Size--) {
points NowPos = q.front();
if(NowPos.first == n && NowPos.second == m) return Step;
q.pop();
for(int i = 0; i < 8; i++) {
int x = NowPos.first + dir[i][0];
int y = NowPos.second + dir[i][1];
if(check(x, y) && !vis[x][y]) {
vis[x][y] = true;
q.push(make_pair(x, y));
}
}
}
Step++;
}
}
int main() {
string StartPos, EndPos;
while(cin >> StartPos >> EndPos) {
int StartX = StartPos[0] - 'a' + 1;
int StartY = StartPos[1] - 48;
n = EndPos[0] - 'a' + 1;
m = EndPos[1] - 48;
memset(vis, 0, sizeof(vis));
while(!q.empty()) q.pop();
q.push(make_pair(StartX, StartY));
vis[StartX][StartY] = true;
cout << "To get from " << StartPos << " to " << EndPos << " takes " << bfs() << " knight moves." << endl;
}
return 0;
}
记录搜索路径
例如刚才的迷宫问题，如何记录最短路径
解决方法可以用数组模拟队列， 使用数组模拟队列的好处是可以用数组的下表来取出其中任何位置的元素，不做队列的pop操作，将其中所有的路径都保存下来，最后输出需要的路径
#include <iostream>
using namespace std;
int PosX[114514];
int PosY[114514];
int PreIndex[114514];
// 三个用来保存路径的数组
// PosX[i] 记录第 i 个点的横坐标
// PosY[i] 记录第 i 个点的纵坐标
// PreIndex[i] 记录第 i 个点前一个点的下标是多少
int n, m, mp[10][10];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
bool vis[10][10];
inline bool check(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int bfs() {
int HeadIndex = 1, NowIndex = 2;
while(HeadIndex < NowIndex) {
int NowX = PosX[HeadIndex];
int NowY = PosY[HeadIndex];
if(NowX == n && NowX == m) return HeadIndex;
// 返回最后达到目标点时队列元素的下标
for(int i = 0; i < 4; i++) {
int x = NowX + dir[i][0];
int y = NowY + dir[i][1];
if(check(x, y) && !vis[x][y] && !mp[x][y]) {
vis[x][y] = true;
PosX[NowIndex] = x;
PosY[NowIndex] = y;
PreIndex[NowIndex] = HeadIndex;
NowIndex++;
// 为当前入队列的元素编号
}
}
HeadIndex++;
// HeadIndex ++ 模拟出队列的操作
}
}
void print(int Index) {
if(!Index) return;
print(PreIndex[Index]);
cout << PosX[Index] << " " << PosY[Index] << endl;
// 递归输出路径
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> mp[i][j];
PosX[1] = 1;
PosY[1] = 1;
PreIndex[1] = 0;
vis[1][1] = true;
print(bfs());
return 0;
}
京公网安备 11010502036488号