题目描述

图中点的层次（求最短距离）
所有边的长度是1-------用宽度搜索求最短边

宽度搜索框架（不断扩展）

queue<----1    //将起始状态插到队列里面
while queue不为空
{
    t<----队头
    扩展t的所有邻点x（能到达的点）
    if(x未被遍历)
    {
        queue<----x;
        d[x]=d[t]+1;
    }
}

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;//邻接表
int q[N];
int d[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int bfs()
{
    int hh=0,tt=0;    //队头、队尾
    q[0]=1;   //第一个元素是起点，令它为1

    memset(d,-1,sizeof(d));    //-1表示没有被遍历过

    d[1]=0;       //遍历过了为0（第一个点是1）


    //框架（这个题是扩展一下当前点的邻边）
    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)    //若j没有被扩展过
            {
                d[j]=d[t]+1;        //扩展这个点（之前的距离加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;
}