数据结构实验之图论二：基于邻接表的广度优先搜索遍历

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2142

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int q[5001];
 4 int d;
 5 void inque(int x)
 6 {
 7     d++;
 8     q[d] = x;
 9 }
10 int main()
11 {
12     int t,n,m,i,j,k,f[101][101],fg[101],a,b;
13     scanf("%d",&t);
14     while(t--)
15     {
16         memset(f,0,sizeof(f));
17         memset(fg,0,sizeof(fg));
18         scanf("%d%d%d", &n,&m,&k);
19         for(i = 1 ;i <= m ; i++)
20         {
21             scanf("%d%d",&a,&b);
22             f[a][b] = 1;
23             f[b][a] = 1;
24         }
25         int p = 0;
26         d = 0;
27         fg[k] = 1;
28         inque(k);
29         do
30         {
31             p++;
32             int flag = 0;
33             for(i = 0; i < n ; i++)
34                 if(!fg[i]&&f[q[p]][i])
35                 {
36                     flag = 1;
37                     inque(i);
38                     fg[i] = 1;
39                 }
40             if(!flag)
41                 break;
42 
43         }while(p!=d);
44         for(i = 1 ; i < d ; i++)
45             printf("%d ",q[i]);
46         printf("%d\n",q[d]);
47     }
48     return 0;
49 }