今天复习bfs。

这是视频连接~

BFS的思路。

标出层次。
来段资料：

bfs全名宽度优先搜索，也称广度优先搜索，可以求出最短路。

bfs可以标出点的层次，Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和bfs类似的思想

宽度优先搜索与队列这种容器紧密结合。

我们看一下bfs是如何遍历图的。
无向图：

有向图：

我们来看看走迷宫这道题。

题目：
给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。
最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。
数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。
输入格式
第一行包含两个整数n和m。
接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围：

1 ≤ n, m ≤ 100

输入样例：

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

输出样例：

8

那我们来想一下怎么解这道题目。
1、模拟队列先复习一下
插入：

q[ ++ tt] = x;

删除：

hh ++;

判断队列是否为空：

hh <= tt;

查询：

q[hh];

接着来复习一下宽搜的模板。
首先我们创建一个队列来表示每次搜到了什么位置。
接着我们写一个while循环：while(队列不空)
然后我们弹出队头。
最后拓展队头即可。
这里的队列有两种写法，1是自己模拟，2是STL。
先说一下模拟，套板子！！！

int hh = 0, tt = -1;
while(hh <= tt)
{
    int t = q[hh ++];
    //拓展队头
}

STL做法的话需要加上头文件#include<queue>

queue<int> q;
while(q.size())
{
    int t = q.front();
    q.pop();
    //弹出队头
}

我们来模拟一下样例。

接下来是代码时间~
没啥可讲直接上代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, g[N][N], d[N][N];
pair<int, int> q[N * N];
int bfs()
{
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q[0] = {0, 0};
    int hh = 0, tt = 0;
    /*
    int hh = 0, tt = -1;
    q[ ++ tt] = {0, 0};
    */
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while(hh <= tt)
    {
        auto t = q[hh ++];
        for(int i = 0 ; i < 4; i ++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && d[x][y] == -1 && g[x][y] == 0)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[ ++ tt] = {x, y};
            }
        }
    }
    return d[n - 1][m - 1];
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> g[i][j];
    cout << bfs() << endl;
    return 0;
}

bfs求最短路

我们可以利用bfs算法给每个点标出层次从而计算点x离点1的距离。

在这个无向图编号为n的点距离1的最短路就是n - 1。
那这么一来就非常简单了。
直接便利一遍就行了，当然图论里的add函数千万别忘！！！

题来了

题目：
给定一个n个点m条边的有向图，图中可能存在重边和自环。
所有边的长度都是1，点的编号为1~n。
1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式
第一行包含两个整数n和m。

接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式
输出一个整数，表示1号点到n号点的最短距离。

数据范围

1 ≤ n, m ≤ 105

输入样例：

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

直接bfs求最短路就行了。
水的不得了/确信
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, h[N], e[N], ne[N], d[N], q[N], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int bfs()
{
    memset(d, -1, sizeof d);
    d[1] = 0;
    q[0] = 1;
    int hh = 0, tt = 0;
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[ ++ tt] = j;
            }
        }
    }
    return d[n];
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl;
    return 0;
}

作业：
1、写一遍今天复习的两道题（默写）

好了这期复习课就到这里了。

未经允许，请勿转载！

这是我的全部分享~

希望读者们对所有分享 + + !

cht会很感谢的。

感谢大家对这几天分享更的慢的谅解~

bye~

附：今天终于修好了电脑

话说这两天声卡他莫名其妙的坏了。
包括扬声器和麦克风。
我太南了
最后把声卡卸载了又重新装了一遍（耗时2小时）
所以今天好不容易回来更分享了。
看在这件事上就给我赞一个吧！
溜了去做下一期的PPT了。
跑了886