宽度优先搜索

宽度优先搜索（又称广度优先搜索，简称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\n",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\n",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)\n") ;  //先输出父节点位置
        printf("(%d,%d)\n" ,d[x].x , d[x].y) ;  //再输出本身位置
        return ;
    }
    print(t) ;   //先输出父节点位置
    printf("(%d,%d)\n" ,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\n",step) ;
    return 0 ;
}