2139=數據結構實驗之圖論五：從起始點到目標點的最短步數（BFS）

 1 #include<stdio.h>
 2 #include<string.h>
 3 int map[1000][1000],visit[1000];
 4 int step,mark;
 5 int queue[1000];//用來儲存已經遍歷了的數據。
 6 void BFS(int k)
 7 {
 8     int i,o=0,p=0,temp,end=0;//temp用來表示當前所在地。o表示下一步從哪個頂點向下出發。
 9     while(o<=p)//p表示在當前一層內有多少個頂點。
10     {
11         temp=queue[o];
12         for(i=1;i<=k;i++)
13         {
14             if(map[temp][i]==1&&visit[i]==0)
15             {
16                 if(i==1){mark=1;return;}
17                 queue[++p]=i;
18                 visit[i]=1;
19             }
20         }
21         if(o==end)//此時表示該層的所有頂點已經遍歷完畢。
22         {
23             step++;//每遍歷完一層步數+1。
24             end=p;//將下一層最后一個頂點放入遍歷順序中。
25         }
26         o++;//遍歷下個頂點。
27     }
28 }
29 int main()
30 {
31     int k,n;
32     while(scanf("%d %d",&k,&n)!=EOF)
33     {
34         mark=0;//用來標記是否達到近衛軍團所在地。
35         step=1;//用來記錄步數。
36         memset(map,0,sizeof(map));
37         memset(visit,0,sizeof(visit));
38         memset(queue,0,sizeof(queue));
39         int i,a,b;
40         for(i=0;i<n;i++)
41         {
42             scanf("%d %d",&a,&b);
43             map[a][b]=1;//單項路徑。
44         }
45         visit[k]=1;//起點已經搜索過。
46         queue[0]=k;//k作為起點，先儲存好。
47         BFS(k);
48         if(mark==1)printf("%d\n",step);
49         else printf("NO\n");
50     }
51 }

轉載于:https://www.cnblogs.com/Angfe/p/10395640.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/278308.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/278308.shtml
英文地址，請注明出處：http://en.pswp.cn/news/278308.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！