2139=数据结构实验之图论五：从起始点到目标点的最短步数（BFS）
生活随笔
收集整理的這篇文章主要介紹了
2139=数据结构实验之图论五：从起始点到目标点的最短步数（BFS）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1 #include<stdio.h>
2 #include<string.h>
3 int map[1000][1000],visit[1000];
4 int step,mark;
5 int queue[1000];//用來儲存已經(jīng)遍歷了的數(shù)據(jù)。
6 void BFS(int k)
7 {
8 int i,o=0,p=0,temp,end=0;//temp用來表示當(dāng)前所在地。o表示下一步從哪個頂點(diǎn)向下出發(fā)。
9 while(o<=p)//p表示在當(dāng)前一層內(nèi)有多少個頂點(diǎn)。
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)//此時表示該層的所有頂點(diǎn)已經(jīng)遍歷完畢。
22 {
23 step++;//每遍歷完一層步數(shù)+1。
24 end=p;//將下一層最后一個頂點(diǎn)放入遍歷順序中。
25 }
26 o++;//遍歷下個頂點(diǎn)。
27 }
28 }
29 int main()
30 {
31 int k,n;
32 while(scanf("%d %d",&k,&n)!=EOF)
33 {
34 mark=0;//用來標(biāo)記是否達(dá)到近衛(wèi)軍團(tuán)所在地。
35 step=1;//用來記錄步數(shù)。
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;//起點(diǎn)已經(jīng)搜索過。
46 queue[0]=k;//k作為起點(diǎn)，先儲存好。
47 BFS(k);
48 if(mark==1)printf("%d\n",step);
49 else printf("NO\n");
50 }
51 }
?
轉(zhuǎn)載于:https://www.cnblogs.com/Angfe/p/10395640.html
總結(jié)
以上是生活随笔為你收集整理的2139=数据结构实验之图论五：从起始点到目标点的最短步数（BFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： php 动态生成文件,php动态程序生成
- 下一篇： Nexus下载构件失败