基于邻接矩阵的广度优先搜索

题目描述

给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）

输入

输入第一行为整数n（0< n <100），表示数据的组数。
对于每组数据，第一行是三个整数k，m，t（0＜k＜100，0＜m＜(k-1)*k/2，0＜ t＜k），表示有m条边，k个顶点，t为遍历的起始顶点。
下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

输出

输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。

示例输入

示例输出

0 3 4 2 5 1

 1 #include<stdio.h>
 2 #include<string.h>
 3 int map[110][110];
 4 int vis[110],que[110];
 5 int m,k,t,flag;
 6 void bfs(int t)
 7 {
 8     int l=0,r=0,tt,j;
 9     que[r++]=t;
10     while(l<r)
11     {
12         tt=que[l++];
13         if(flag==1)
14         {
15             printf("%d",tt);
16             flag=0;
17         }
18         else
19         printf(" %d",tt);
20         for(j=0;j<k;j++)
21         {
22             if(!vis[j]&&map[tt][j])
23             {
24                 que[r++]=j;
25                 vis[j]=1;
26             }
27         }
28     }
29 }
30 int main()
31 {
32     int n,i,u,v;
33     scanf("%d",&n);
34     while(n--)
35     {
36         memset(vis,0,sizeof(vis));
37         memset(map,0,sizeof(map));
38         scanf("%d %d %d",&k,&m,&t);
39         for(i=0;i<m;i++)
40         {
41             scanf("%d %d",&u,&v);
42             map[u][v]=map[v][u]=1;
43         }
44         flag=1;
45         vis[t]=1;
46         bfs(t);
47         printf("\n");
48     }
49     return 0;
50 }

View Code