SDUT 2141 【TEST】数据结构实验图论一：基于邻接矩阵的广度优先搜索遍历

数据结构实验图论一：基于邻接矩阵的广度优先搜索遍历

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

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

Input

输入第一行为整数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顶点的无向边。

Output

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

Example Input

Example Output

0 3 4 2 5 1

Hint

以邻接矩阵作为存储结构。

DQE:

邻接矩阵表示图的广度优先搜索，借助队列实现。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <climits>
 5 
 6 using namespace std;
 7 
 8 #define MVN 110
 9 
10 typedef struct AdjMatrix
11 {
12     int w;
13     char *info;
14 }AM;
15 
16 typedef struct MGraph
17 {
18     int vex[MVN];
19     AM arc[MVN][MVN];
20     int vexnum,arcnum;
21     int k;
22 }MG;
23 
24 void creat(MG &G)
25 {
26     int i,j,k;
27     for(k=0;k<G.vexnum;k++)
28     {
29         G.vex[k]=k;
30     }
31     for(k=0;k<G.arcnum;k++)
32     {
33         scanf("%d %d",&i,&j);
34         G.arc[i][j].w=G.arc[j][i].w=1;
35     }
36 }
37 
38 void BFS(MG &G)
39 {
40     queue <int> Q;
41     int i,k;
42     bool visited[MVN]={false};
43     for(k=0;k<G.vexnum;k++)
44     {
45         if(G.vex[k]==G.k)
46             break;
47     }
48     Q.push(k);
49     while(!Q.empty())
50     {
51         i=Q.front();
52         Q.pop();
53         if(!visited[i])
54         {
55             if(i==G.k)
56                 printf("%d",G.vex[i]);
57             else
58                 printf(" %d",G.vex[i]);
59             visited[i]=true;
60             for(k=0;k<G.vexnum;k++)
61             {
62                 if(G.arc[i][k].w>0)
63                     Q.push(k);
64             }
65         }
66     }
67     printf("
");
68 }
69 
70 int main()
71 {
72     int t;
73     scanf("%d",&t);
74     while(t--)
75     {
76         MG G={0};
77         scanf("%d %d %d",&G.vexnum,&G.arcnum,&G.k);
78         creat(G);
79         BFS(G);
80     }
81     return 0;
82 }
83 
84 /***************************************************
85 User name: ***
86 Result: Accepted
87 Take time: 0ms
88 Take Memory: 344KB
89 Submit time: 2016-11-13 18:54:57
90 ****************************************************/