给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式

输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式

按照”{ v1 v2 … vk}”的格式，每行输出一个连通集。先输出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 }

代码实现

C语言

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 11
typedef int Vertex;
Vertex Visited[MaxVertexNum];

typedef struct GNode *PtrToGNode;   // 图节点
struct GNode {
	int Nv;
	int Ne;
	int G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;

MGraph CreateGraph( int VertexNum ) {   // 初始化图
	Vertex V, W;
	MGraph Graph;
	Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	for ( V=0; V<Graph->Nv; V++ ) {
		for ( W=0; W<Graph->Nv; W++ ) {
			Graph->G[V][W] = 0;
		}
	}
	return Graph;
}

typedef struct ENode *PtrToENode;
struct ENode {  // 边节点
	Vertex V1, V2;
	int Weight;
};
typedef PtrToENode Edge;

void InsertEdge( MGraph Graph, Edge E ) {   // 给边赋权重
	Graph->G[E->V1][E->V2] = E->Weight;
	Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph() {   // 根据题目建立图
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
	
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
	scanf("%d", &(Graph->Ne));
	if ( Graph->Ne != 0 ) {
		E = (Edge)malloc(sizeof(struct ENode));
		for ( i=0; i<Graph->Ne; i++ ) {
			scanf("%d %d", &E->V1, &E->V2);
			E->Weight = 1;
			InsertEdge( Graph, E );
		}
	}
	return Graph;
}

void DFS ( MGraph Graph , Vertex V) {   // 深度遍历
	Visited[V] = 1;
	printf("%d ", V);
	for ( Vertex j=0; j<Graph->Nv; j++ ) {
		if ( Graph->G[V][j] == 1 && Visited[j] == 0 ) {
			DFS(Graph, j);
		}
	}	
}

struct {    // 创建队列节点
	Vertex Vert[MaxVertexNum];
	int rear;
	int front;
} Q;

void CreateQ() {    // 初始化队列
    Q.rear = 0;
    Q.front = 0;
    for ( int i=0; i<MaxVertexNum; i++ ) {
        Q.Vert[i] = -1;
    }
}

void AddQ(Vertex V) {   // 队列push节点
	if ( (Q.rear+1) % MaxVertexNum == Q.front ) {
		printf("The queue is full.\n");
	} else {
		Q.rear = (Q.rear+1) % MaxVertexNum;
		Q.Vert[Q.rear] = V;
	}
}

Vertex DelQ() { // 队列pop节点
	if ( Q.front == Q.rear ) {
		printf("The queue is empty.\n");
		return -1;
	} else {
		Q.front = (Q.front+1) % MaxVertexNum;
		return Q.Vert[Q.front];
	}
}


void BFS ( MGraph Graph , Vertex V ) {  // 广度遍历
    Vertex T;
    AddQ(V);
    Visited[V] = 1;
    while ( Q.front != Q.rear ) {
        T = DelQ();
        printf("%d ", T);
        for ( Vertex j=0; j<Graph->Nv; j++ ) {
            if ( Graph->G[T][j] == 1 && Visited[j] == 0 ) {
                AddQ(j);
                Visited[j] = 1;
            }
        }
    }
}

void InitVisit() {  // 标记节点是否被访问过。此为初始化。
    for ( int i=0; i<MaxVertexNum; i++ ) Visited[i] = 0;
}

int main() {
	MGraph Graph;
	Graph = BuildGraph();

	Vertex V = 0;
    InitVisit();
	for ( V=0; V<Graph->Nv; V++ ) {
		if ( Visited[V] == 0 ) {
			printf("{ ");
			DFS ( Graph, V);
			printf("}\n");
		}
	}

    CreateQ();
    InitVisit();
    for ( V=0; V<Graph->Nv; V++ ) {
        if ( Visited[V] == 0 ) {
            printf("{ ");
            BFS ( Graph, V);
            printf("}\n");
        }
    }

	return 0;
}