7-6 列出连通集 (25 分)
给定一个有$N$个顶点和$E$条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到$N$−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数$N(0<N \leq 10)$和$E$，分别是图的顶点数和边数。随后$E$行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照”{$ v_1 v_2 \dots v_k $}”的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例:
1
2
3
4
5
6
7
| 8 6
0 7
0 1
2 0
4 1
2 4
3 5
|
输出样例:
1
2
3
4
5
6
| { 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include<stdio.h>
#include<stdlib.h>
#define MAXVEX 15
void CreateGraph( );
void DFS( int i);
void DFSTraverse();
void BFSTraverse();
int G[MAXVEX][MAXVEX],Nv,Ne;
int visited[MAXVEX];
int main()
{
CreateGraph();
DFSTraverse();
BFSTraverse();
return 0;
}
void CreateGraph()
{
int i,j;
int v1,v2;
scanf("%d %d",&Nv,&Ne);
for( i=0; i<Nv; i++)
{
for( j=0; j<Nv; j++)
{
G[i][j] = 0;
}
}
for( i=0; i<Ne; i++)
{
scanf("%d %d",&v1,&v2);
G[v1][v2] = 1;
G[v2][v1]= G[v1][v2];
}
}
void DFS( int i)
{
int j;
visited[i] = 1;
printf("%d ",i);
for( j=0; j<Nv; j++)
{
if( G[i][j] && !visited[j])
{
DFS (j);
}
}
}
void DFSTraverse( )
{
int i;
for( i=0; i<Nv; i++)
{
visited[i] = 0;
}
for ( i=0; i<Nv; i++)
{
if( !visited[i])
{
printf("{ ");
DFS(i);
printf("}\n");
}
}
}
void BFSTraverse( )
{
int q[MAXVEX]={0};
int rear=-1,front=-1;
int i,j;
int temp;
for( i=0; i<Nv; i++)
{
visited[i] = 0;
}
for( i=0; i<Nv; i++){
if( !visited[i]){
printf("{ ");
visited[i] =1;
q[++rear] = i;
while( front<rear ){
temp =q[++front];
printf("%d ",temp);
for( j=0; j<Nv;j++){
if( G[temp][j] && !visited[j]){
visited[j] = 1;
q[++rear] = j;
}
}
}
printf("}\n");
}
}
}
|
