BFS-宽度优先搜索（Breadth First Search）—1

Bertha 。 2022-07-11 13:21 169阅读 0赞

在这篇博客[http://blog.csdn.net/hacker\_zhidian/article/details/54774013][http_blog.csdn.net_hacker_zhidian_article_details_54774013]中的问题我们采用了深度优先搜索（dfs）来解决，其实还有另外一种方法也可以解决并且速度比dfs更快，这就是宽度优先搜索，让我们一起来看看吧：

有一个迷宫，迷宫状态通过一个二维数组储存，给出二维数组的行总数和列总数和对应坐标的数据，求出从开始点（坐标为0，0）到结束点（最后一行给出的点的坐标）所需的最短路径，样例数据：  
5 4  
0 0 1 0  
0 0 0 0  
0 0 1 0  
0 1 0 0  
0 0 0 1  
3 2

宽度优先搜索解决本题的基本思想是对当前点进行扩展，将扩展出来的下一步所有可能的情况都加入一个队列（一种先进先出的数据结构）中，
    然后再分别对每种可能的情况再进行招展筛选并再加入队列中，直到筛选的点达到目标点。

首先，我们一开始在（0, 0）坐标点，我们要到达数组下标为a\[3\]\[2\]这个点，在（0, 0）点的时候，我们可以向右走（0, 1）或者向下走（1, 0），当我们在（0, 1）的时候我们只能向下走（右边为 1 不能通过），当我们在（1, 0）的时候我们可以向下走（2, 0），因为（1, 1）已经先被走过了，再走过去也不会有更短的路径。。。  
那么什么时候结束扩展呢，当然是到达目标点的时候或者所有的点都扩展完了的时候。那我们就可以架构出大致的代码：

for(int i = 0; i < 4; i++)  // 对当前下一个坐标点进行扩展
        {
            nX = que[head].x + next[i][0];
            nY = que[head].y + next[i][1];
            if(nX < 0 || nX >= n || nY < 0 || nY >= m)  // 检测越界
            {
                continue;
            }
            if(map[nX][nY] == 0 && book[nX][nY] == 0)    // 如果能通过
            {
                book[nX][nY] = 1; // 因为我们是队列，所以不需要取消标记，看谁先走到这个点谁就是最短路径（至少是最短之一，因为可能有重复）
                que[tail].x = nX;
                que[tail].y = nY;   // 更新坐标点
                que[tail].s = que[head].s + 1;  // 走过的路径加一
                tail++;
                if(nX == toX && nY == toY)   // 到达目标点则激活标记并且跳出循环
                {
                    flag = 1;
                    break;
                }
            }
        }

代码中，我们用一个数组que来储存坐标点数据，que为坐标点储存队列，包含了 x 坐标 y 坐标和已经走过了的路径长度，head模拟队头指针。ok，这里写出了对当前坐标点的扩展，但是我们不能无限制的扩展下去，什么时候结束扩展呢，当然是当队列中没有坐标点的情况下结束（好像有点傻的问题），所以外层还需要套一层循环：

while(head < tail)
        {
            int nX, nY;
            int flag = 0;   // 标记是否到达目标点
            for(int i = 0; i < 4; i++)  // 对当前下一个坐标点进行扩展
            {
                nX = que[head].x + next[i][0];
                nY = que[head].y + next[i][1];
                if(nX < 0 || nX >= n || nY < 0 || nY >= m)  // 检测越界
                {
                    continue;
                }
                if(map[nX][nY] == 0 && book[nX][nY] == 0)    // 如果能通过
                {
                    book[nX][nY] = 1;
                    que[tail].x = nX;
                    que[tail].y = nY;   // 更新坐标点
                    que[tail].s = que[head].s + 1;  // 走过的路径加一
                    que[tail].f = head;
                    tail++;
                    if(nX == toX && nY == toY)   // 到达目标点则激活标记并且跳出循环
                    {
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag == 1)
            {
                break;
            }
            head++; // 当前节点筛选完成，节点出队列
        }

当队列头指针和尾指针相同的时候就一定要结束了，好了，大致的我们都完成了，下面给出完整代码：

#include <iostream>
    using namespace std;
    
    int n = 5, m = 4;   // 地图数组的总行数和总列数
    int map[100][100] = {   // 地图数组
        {
       0, 0, 1, 0},
        {
       0, 0, 0, 0},
        {
       0, 0, 1, 0},
        {
       0, 1, 0, 0},
        {
       0, 0, 0, 1}
    };
    int toX = 3, toY = 2;   // 目标点坐标
    int book[100][100];     // 标记数组
    
    struct node // 节点数据结构
    {
        int x;  // x坐标
        int y;  // y坐标
        int s;  // 走过的路径
        int f;
    };
    int head, tail; // 模拟队列的头尾指针
    node que[10000];    // 储存节点的队列
    
    
    int next[4][2] = {
        {-1, 0}, // 上
        {
       0, 1}, // 右
        {
       1, 0}, // 下
        {
       0, -1}  // 左
    };
    
    void bfs()
    {
        que[tail].x = 0;
        que[tail].y = 0;
        que[tail].s = 0;    // 将第一个坐标点入队
        tail++;
        while(head < tail)
        {
            int nX, nY;
            int flag = 0;   // 标记是否到达目标点
            for(int i = 0; i < 4; i++)  // 对当前下一个坐标点进行扩展
            {
                nX = que[head].x + next[i][0];
                nY = que[head].y + next[i][1];
                if(nX < 0 || nX >= n || nY < 0 || nY >= m)  // 检测越界
                {
                    continue;
                }
                if(map[nX][nY] == 0 && book[nX][nY] == 0)    // 如果能通过
                {
                    book[nX][nY] = 1;
                    que[tail].x = nX;
                    que[tail].y = nY;   // 更新坐标点
                    que[tail].s = que[head].s + 1;  // 走过的路径加一
                    que[tail].f = head;
                    tail++;
                    if(nX == toX && nY == toY)   // 到达目标点则激活标记并且跳出循环
                    {
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag == 1)
            {
                break;
            }
            head++; // 当前节点筛选完成，节点出队列
        }
    }
    
    int main()
    {
        cin >> n >> m;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                cin >> map[i][j];
            }
        }
        cin >> toX >> toY;
    
        bfs();
        cout << que[tail - 1].s << endl;    // 输出队尾前一个元素坐标点的路径数（代码58行，队列先赋值之后队尾指针加一）
    
        return 0;
    }

让我们来看一下结果：  
![这里写图片描述][SouthEast]

Nice，完成！  
一般来说，循环是会比递归快的，因为递归还有调用函数的栈开销，即使是内联函数也没有相同情况下的循环快。好了，如果博客中有不对的地方还请多多指点。  
谢谢观看。。。

[http_blog.csdn.net_hacker_zhidian_article_details_54774013]: http://blog.csdn.net/hacker_zhidian/article/details/54774013
[SouthEast]: /images/20220711/4f1acb0a7a7441a79346ef0e4dd4a793.png