一、图的BFS

1、思路

上图中的遍历顺序就是以A为起点开始的广度优先搜索。先遍历距离A点最近的距离，然后再依次向外拓展。

2、模板

（1）问题

题目当中提到了最短路，同时每条边的权重都是1，同时在边权为1的情况下，我们的广度优先搜索是具备最短路的性质的。因此，我们采用BFS去做这道题。而最短路的证明，在前面讲解DFS和BFS的时候证明过，大家可以自行去看，这里附上链接：

同时，在该文章中，我还为大家介绍了，为什么BFS要用队列，如何保证搜到的是最短的等等常见问题：

DFS与BFS保姆级教学

（2）代码模板

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10;
const int M=3e5+10;
int h[N],e[M],ne[M],idx;
int m[N];
int n,k;
void add(int x,int y)
{
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}
int bfs()
{
    queue<int>q;
    q.push(1);
    m[1]=0;
    while(!q.empty())
    {
        for(int i=h[q.front()];i!=-1;i=ne[i])
        {
            if(m[e[i]]==-1)
            {
                m[e[i]]=m[q.front()]+1;
                q.push(e[i]);
            }
            if(e[i]==n)goto A;
        }
        q.pop();
    }
    A:
    return m[n];
}
int main()
{
    memset(h,-1,sizeof h);
    memset(m,-1,sizeof m);
    cin>>n>>k;
    for(int i=0;i<k;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cout<<bfs();
    return 0;
}

（3）代码解析