宽度优先搜索（又称广度优先搜索，简称BFS），一种先生成的节点，先扩展的策略。
搜索过程：从初始节点开始逐层向下扩展，在第n层节点还没搜索结束之前，不能进入第n+1层搜索（需要使用队列实现）
（1） 把初始节点放入到队列中
（2） 如果队列为空，则问题无解，跳出循环
（3） 取出队列中的第一个元素，并记该节点为cur，并将队列第一个元素删除
（4） 考察cur节点是否为目标节点，如果是目标节点则问题解决，跳出循环
（5） 若节点cur不能扩展则跳到第二步；
（6） 若节点cur可以扩展，将其子节点放入队列的尾部，跳到第二步
例题：走迷宫问题
给定一个二维数组 int map[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 ,
} ;
它表示一个迷宫，其中“1”表示墙壁，“0”表示可以走的路，只能横着走或者竖着走，不能斜着走，要求编写程序求出从左上角到右下角的最短路径的长度,例如上述问题输出结果为：8
#include
#include
#include
#include
#include
using namespace std ;
int a[100][100] , vis[100][100] = {0} ;
int m , n ;
struct dot{
int x ;
int y ;
int step ;
};
int dx[] = {-1,0,1,0} ;
int dy[] = {0,1,0,-1} ;
bool is_ok(dot cur) {
if(cur.x < 0|| cur.x >= m || cur.y < 0 || cur.y >= n )
return 0 ;
return 1 ;
}
int bfs() {
dot A ;
A.x = 0 ;
A.y = 0 ;
A.step = 0 ;
vis[0][0] = 1 ;
queue q ;
while(!q.empty())
q.pop() ;
q.push(A) ;
while(!q.empty()) {
dot cur = q.front() ;
q.pop();
if(cur.x == m-1 && cur.y == n-1)
return cur.step ;
dot next ;
for(int i = 0 ; i < 4 ; i++) {
next.x = cur.x + dx[i] ;
next.y = cur.y + dy[i] ;
next.step = cur.step + 1 ;
if(is_ok(next)&&a[next.x][next.y] != 1&&vis[next.x][next.y] != 1) {
q.push(next) ;
vis[next.x][next.y] = 1 ;
}
}
}
return 0 ;
}
int main() {
scanf("%d%d",&m,&n) ;
int i , j , k ;
for(i = 0 ; i < m ; i++)
for(j = 0 ; j < n ; j++)
scanf("%d",&a[i][j]) ;
int step = bfs() ;
printf("%d
",step) ;
return 0 ;
}
当节点足够多时，有可能会超出队列的容量，程序在运行时就会出错，所以也可以使用数组代替队列。
#include
#include
#include
#include
using namespace std ;
int a[100][100] , vis[100][100] = {0} ;
int m , n ;
struct dot{
int x ;
int y ;
int step ;
}d[10000];
int dx[] = {-1,0,1,0} ;
int dy[] = {0,1,0,-1} ;
bool is_ok(dot cur) {
if(cur.x < 0|| cur.x >= m || cur.y < 0 || cur.y >= n )
return 0 ;
return 1 ;
}
int bfs() {
dot A ;
A.x = 0 ;
A.y = 0 ;
A.step = 0 ;
vis[0][0] = 1 ;
int head = 0 , tail = 0 ;
d[tail++] = A ;
while(head < tail) {
dot cur = d[head++] ;
if(cur.x == m-1 && cur.y == n-1)
return cur.step ;
dot next ;
for(int i = 0 ; i < 4 ; i++) {
next.x = cur.x + dx[i] ;
next.y = cur.y + dy[i] ;
next.step = cur.step + 1 ;
if(is_ok(next)&&a[next.x][next.y] != 1&&vis[next.x][next.y] != 1) {
d[tail++] = next ; ;
vis[next.x][next.y] = 1 ;
}
}
}
return 0 ;
}
int main() {
scanf("%d%d",&m,&n) ;
int i , j , k ;
for(i = 0 ; i < m ; i++)
for(j = 0 ; j < n ; j++)
scanf("%d",&a[i][j]) ;
int step = bfs() ;
printf("%d
",step) ;
return 0 ;
}
如果想输出所走的路径，可以先记录各个节点的父节点位置，然后递归输出路径：
#include
#include
#include
#include
using namespace std ;
int a[100][100] , vis[100][100] = {0} ;
int m , n ;
struct dot{
int x ;
int y ;
int step ;
}d[10000];
int pre[10000] ;
int dx[] = {-1,0,1,0} ;
int dy[] = {0,1,0,-1} ;
bool is_ok(dot cur) {
if(cur.x < 0|| cur.x >= m || cur.y < 0 || cur.y >= n )
return 0 ;
return 1 ;
}
void print(int x) { //递归输出
int t = pre[x] ;
if(t == 0) {
printf("(0,0)
") ; //先输出父节点位置
printf("(%d,%d)
" ,d[x].x , d[x].y) ; //再输出本身位置
return ;
}
print(t) ; //先输出父节点位置
printf("(%d,%d)
" ,d[x].x , d[x].y) ; //再输出本身位置
}
int bfs() {
dot A ;
A.x = 0 ;
A.y = 0 ;
A.step = 0 ;
vis[0][0] = 1 ;
int head = 0 , tail = 0 ;
d[tail++] = A ;
while(head < tail) {
dot cur = d[head++] ;
if(cur.x == m-1 && cur.y == n-1) {
print(head-1) ;
return cur.step ;
}
dot next ;
for(int i = 0 ; i < 4 ; i++) {
next.x = cur.x + dx[i] ;
next.y = cur.y + dy[i] ;
next.step = cur.step + 1 ;
if(is_ok(next)&&a[next.x][next.y] != 1&&vis[next.x][next.y] != 1) {
pre[tail] = head - 1 ; //记录该节点的父节点所在位置
d[tail++] = next ; ;
vis[next.x][next.y] = 1 ;
}
}
}
return 0 ;
}
int main() {
scanf("%d%d",&m,&n) ;
int i , j , k ;
for(i = 0 ; i < m ; i++)
for(j = 0 ; j < n ; j++)
scanf("%d",&a[i][j]) ;
int step = bfs() ;
printf("%d
",step) ;
return 0 ;
}