算法

广度优先搜索

用单链表储存树和图时，从每一个节点的头指针只能储存当前节点能到达的下一层的节点
宽度优先遍历没有进行递归所以每一次搜索都是以头结点指向的位置。

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

C++ 代码

#include<iostream>
usinga namespace std;
const int N=100010;
int n,tt=0,hh=0,m,idx=0;//头指针尾指针和插入的第几个数 
int e[N],ne[N],q[N];
int d[N],h[N];//d[N]表示每个节点离1的距离 
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;//插入操作 
}
void bfs()
{
    q[0]=1;
    memset(d,-1,sizeof(d));
    d[1]=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;//当前节点的根节点的距离加1 
                q[++tt]=j;//插入队列中 
            }
        }
    }
    cout<<d[n]<<endl;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    bfs();
    return 0;
}