树和图的宽度优先遍历与深度优先遍历

 1 //用单链表储存树和图时，从每一个节点的头指针只能储存当前节点能到达的下一层的节点 
 2 //宽度优先遍历没有进行递归所以每一次搜索都是以头结点指向的位置 
 3 //例如  1->2  1->3  1->5  2->8  3->6  3->7
 4 //即h[1]->5->3->2->-1;
 5 //h[2]->8->-1;
 6 //h[3]->7->6->-1;
 7 //宽度遍历和深度遍历的区别就是
 8 //深度优先遍历每搜一次就进入递归调用自身，使得搜索的节点的头指针发生变化即变成了指向当前节点的头指针
 9 //然后就变成了搜索此节点能到达的下一层
10 //宽度优先遍历没有进行递归也就是一直搜索当前节点能到达的下一层节点直到节点搜索完时再搜索下一节点 
11 #include<iostream>
12 #include<algorithm>
13 #include<cstring>
14 using namespace std;
15 const int N=100010;
16 int n,tt=0,hh=0,m,idx=0;
17 int e[N],ne[N],q[N];
18 int d[N],h[N];
19 void add(int a,int b)
20 {
21     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
22 }
23 void bfs()
24 {
25     q[0]=1;
26     memset(d,-1,sizeof(d));
27     d[1]=0;
28     while(hh<=tt)
29     {
30         int t=q[hh++];
31         for(int i=h[t];i!=-1;i=ne[i])
32         {
33             int j=e[i];
34             if(d[j]==-1)
35             {
36                 d[j]=d[t]+1;
37                 q[++tt]=j;
38             }
39         }
40     }
41     cout<<d[n]<<endl;
42 }
43 int main()
44 {
45     memset(h,-1,sizeof h);
46     cin>>n>>m;
47     for(int i=1;i<=m;i++)
48     {
49         int a,b;
50         cin>>a>>b;
51         add(a,b);
52     }
53     bfs();
54     return 0;
55 }