广度优先搜索算法(Breadth-First-Search，BFS)也是一种图的搜索算法，它跟我们之前学习的DFS区别在于，DFS是沿着一条路或者一个分支一路遍历下去，直到最深的分支节点或者路的尽头，再往回回溯，遍历其他的分支或者其他路，直到找到目标为止；然而DFS是由起点先遍历与它相邻的点，再往外遍历相邻点的相邻的点，一直往外扩散，直到找到终点或者遍历完整张图。

例子：

一个4*6矩阵，起始点在(0,0)左上角，终点在(3,5)右下角，BFS如何从起始点搜索到终点？

每个格子都是从上下左右的顺序搜索，遍历到的格子都会放入队列中，按照先进先出的逻辑来遍历，遍历到的格子会标记为已经访问过，不会再进入队列中，下图紫色的格子代表当前出队列遍历周围的格子。

从入口开始，将入口放入队列，标记已访问；如果队列不为空或者没有找到终点会一直循环下去；将队列的格子(0,0)出队列，遍历上下左右的格子，上和左都超出了地图，将下(1,0)和右(0,1)放入队列且标记已访问；以下的图就是按照这个逻辑来进行往外扩散。

最后找到了终点，程序结束。

实现代码：

/*入口坐标 Start出口坐标 End地图 pMap地图宽 nWidth地图高 nHeight通行标记 .阻碍标记 X*/struct position {    int x;    int y;};bool BFS(char** pMap, int nWidth, int nHeight, position Start, position End) {    int nstep[][2] = {{0,-1}, {0,1}, {-1,0}, {1,0}};//上下左右    bool vist[100][100];//用来标记走过的格子    memset(vist, 0, sizeof(vist));    queue<position> q;//存放格子的队列    q.push(Start);    vist[Start.x][Start.y] = 1;    while(!q.empty()) {        position p = q.front();        q.pop();        if(p.x == End.x && p.y == End.y) { //判断是否为终点            return true;        }        for(int i=0; i<4; i++) { //走当前格子的四个方向            position next;            next.x = p.x + nstep[i][0];            next.y = p.y + nstep[i][1];            if(next.x >= 0 && next.x < nWidth && next.y >= 0 && next.y < nHeight &&                 vist[next.x][next.y] == 0) { //判断是否超出格子和走过的格子                if(pMap[next.x][next.y] == '.') { //存入可走的格子                    vist[next.x][next.y] = 1;                    q.push(next);                }            }        }    }    return false; //遍历完能走的格子没有找到终点}

公众号有系列文章