广度搜索的原理是把一个节点放入队列，然后从队列中取出来处理，处理后将与其相邻的节点放入队列中，等待被处理，然后继续从队列中取出一个节点处理，处理后将与其相邻的节点放入队列中，如此循环，直到把所有的点都处理完。

        如下图，先把1入队列，然后队列中取出队首，就是1，处理1

        遍历与1其相邻的节点，把他们放入队列待处理，1处理完后，再从队列中取队首，就是2，2没有其他相邻未处理节点了，就继续取队首的3，并把与3相邻的节点5放入队列，处理3

        然后把5取出来，把4，6放入队列，处理5，之后从队列里依次取4和6处理，这样整个图就处理完了

标记与剪枝

        标记，就是说如果这个节点之前已经处理过了，就标记一下，下次不需要再处理这个节点，剪枝则相对等于树的遍历来说，假如一个节点处理后发现不符合要求，则其子节点也不再需要处理了，类似把子树剪了一样，就是剪枝。标记与剪枝能加快遍历的速度。

最短路径

        如下图，求任意一点到8的最短路径

        分析，这里的最短路径可以使用经典最短路径算法做，也可以用广度搜索法做，经典最短路径算法其实也是广度搜索的一种方式，由于这个图中的边权重都是一样的，因此可以用经典广度搜索算法做：

        比如从2开始出发，则先把2放入队列中，把2记录下来，然后把与2相连的节点1，4放入队列中

        取1，把2，3放入队列中，因为2已经处理过，因此忽略

        取4，把6，7放入队列

        取3，把5，7放入队列，因为7已经在队列中了，因此忽略

        取6，因为6可以到达8，因此结束，因为这里边的权是一样大的，因此先到达的路径就是最短路径之一，只要记录经过的点并打印出来就是最短路径。

        代码如下：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int que[100] = {0}; //队列
int lujin[100] = {0}; //记录路径
int flag[8] = {0}; //标记
int line[8][8] = {0}; //路径矩阵

void toline(int s, int e) {
    line[s][e] = 1;
    line[e][s] = 1;
}

typedef struct{
    int pos;
    vector<int> lujin; //记录路径
}Point;

int main () {
    toline(0,1);
    toline(0,2);
    toline(1,3);
    toline(2,4);
    toline(2,6);
    toline(3,5);
    toline(3,6);
    toline(4,6);
    toline(5,7);
    toline(6,7);

    queue<Point>  que;

    Point p;
    p.pos = 0; //开始位置
    p.lujin.emplace_back(p.pos); //放入路径
    que.emplace(p);
    while (que.size()) {
        p = que.front(); //取队首
        que.pop();
        flag[p.pos] = 1; //标记
        for (int i = 0; i < 8; i++) //遍历找连通的
        {   
            if (flag[i] != 1 && line[p.pos][i] == 1)
            {
                Point pnew;
                pnew.pos = i;
                pnew.lujin = p.lujin; //拷贝路径
                pnew.lujin.emplace_back(i); //增加这个点
                que.emplace(pnew);
                if (i == 7) //已经达到终点
                {
                    for (auto &it : pnew.lujin) //打印路径
                        cout << it << " ";
                    return 0;
                }
            }
        }
    }
    return 0;
}
//输出结果
0 2 6 7

迷宫问题

        如下图从A点出发走到B点，只能向左和向下走，列举出所有的方案。对于这类题目，可以使用其他方法解，这里讨论使用广度搜索的方式解答。

        分析可知，这个题目与上一个题目基本类似，每个格子算是一个节点，因为只能向下和向左走，因此某个节点左边和下面的白色格子是其相邻节点，也可以看成是其子节点。

        首先把A点入队列，然后取出来，枚举其子节点入队，然后循环从队列中取出节点，枚举子节点入队，如此循环直至队列中没有节点，如果取到B节点，则打印出其路径，得到一个解。这里由于需要枚举所有的路径，且只能向左向下，因此入队列的时候不需要保证队列里没有该点，也不需要标记该点已经处理过。

        代码如下：

#include <iostream>
#include <vector>
using namespace std;

 typedef struct{
    int x;
    int y;
    vector<pair<int, int>> lujin; //记录路径
}Point;

int mmap[6][6] = {0};

int main () {
    mmap[0][1] = 1;
    mmap[1][4] = 1;
    mmap[2][0] = 1;
    mmap[2][2] = 1;
    mmap[3][3] = 1;
    mmap[3][4] = 1;
    mmap[4][0] = 1;
    mmap[4][2] = 1;

    vector<Point> que;
    Point p;
    p.x = 0;
    p.y = 0;
    p.lujin.emplace_back(make_pair(0,0));
    que.emplace_back(p);
    
    while (que.size())
    {
        auto it = que.begin();
        Point f = *it;
        que.erase(it);

        //看下边
        if (mmap[f.x+1][f.y] == 0 && f.x < 5)
        {
            Point pnew;
            pnew.x = f.x+1;
            pnew.y = f.y;
            pnew.lujin = f.lujin;
            pnew.lujin.emplace_back(make_pair(pnew.x, pnew.y));
            if (pnew.x == 5 && pnew.y == 5)
            {
                for (auto &it : pnew.lujin) //打印路径
                    cout << "(" << it.first << "," << it.second << ")" << " ";
                cout << endl;
            } 
            else
                que.push_back(pnew);
        }
        //看左边
        if (mmap[f.x][f.y+1] == 0 && f.y < 5)
        {
            Point pnew;
            pnew.x = f.x;
            pnew.y = f.y+1;
            pnew.lujin = f.lujin;
            pnew.lujin.emplace_back(make_pair(pnew.x, pnew.y));
            if (pnew.x == 5 && pnew.y == 5)
            {
                for (auto &it : pnew.lujin) //打印路径
                    cout << "(" << it.first << "," << it.second << ")" << " ";
                cout << endl;
            } 
            else
                que.push_back(pnew);
        }
    }
    
    return 0;
}
//输出结果
(0,0) (1,0) (1,1) (2,1) (3,1) (4,1) (5,1) (5,2) (5,3) (5,4) (5,5) 
(0,0) (1,0) (1,1) (1,2) (1,3) (2,3) (2,4) (2,5) (3,5) (4,5) (5,5)

相邻问题

        如下图表格，1表示陆地，0表示海洋，如果某一陆地上下左右相邻格都是1，则他们属于同一块大陆，请统计下图中有多少块不同的大陆

        分析：这题可以通过广度搜索来统计，先从第一格开始，如果是1，则入队列，然后从队列中取出，获取其上下左右为1的格子放入队列，直到队列为空，则找到一块完整的大陆，继续遍历所有格子找出所有的大陆，使用标记法来进行剪枝，已经搜过的格子不用再次处理。

        代码如下

#include <iostream>
#include <queue>
using namespace std;

int arr[10][10] = {{1,1,1,1,1,1,0,0,0,1},{1,0,1,0,1,1,0,1,0,1},
{1,0,1,1,1,1,0,1,1,1},{0,0,0,0,1,1,0,0,1,1},{0,1,0,0,1,0,0,0,1,0},
{0,1,0,0,0,1,0,0,1,0},{1,1,0,0,0,1,1,1,0,0},{1,1,1,0,0,0,1,0,0,0},
{1,0,1,1,0,0,1,0,1,1},{0,0,1,1,1,0,1,0,1,0}};

int flag[100] = {0};
queue<int> que;

void findblock() {
    do
    {
        int i = que.front();
        flag[i] = 1;
        cout << i << " ";
        que.pop();
        int row = i/10;
        int col = i%10;
        //搜索上下左右（bfs）
        if (row > 0 && flag[i-10] == 0 && arr[row-1][col] == 1)
            que.push(i-10); //上
        if (i+10 < 100 && flag[i+10] == 0 && arr[row+1][col] == 1)
            que.push(i+10); //下
        if (col > 0 && flag[i-1] == 0 && arr[row][col-1] == 1)
            que.push(i-1); //左
        if (col < 9 && flag[i+1] == 0 && arr[row][col+1] == 1)
            que.push(i+1);
    } while (!que.empty());
    cout << endl;
}

int main() {
    int block = 0;
    for (size_t i = 0; i < 100; i++)
    {
        int row = i/10;
        int col = i%10;
        if (arr[row][col] == 1 && flag[i] == 0)
        {
            que.push(i);
            block++;
            findblock();
        }
    }
    cout << "num:" << block << endl;
    return 0;
}
//输出结果：
0 10 1 20 2 12 3 22 4 23 14 5 24 24 15 15 34 25 34 25 25 25 44 35 35 44 35 35 35 35 
9 19 29 39 28 38 38 27 48 48 17 58 58
41 51 61 71 60 70 72 70 80 82 80 92 83 93 93 94 94
55 65 66 76 67 86 96
88 98 89
num:5