数据结构刷题笔记2——使用DFS和BFS列出连通集

06-图1 列出连通集 (25 分)——PTA

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

输入格式:

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

输出格式:

按照"{ v1 v2 ... *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 }

题目理解

本题给了我们几组数据用来建图,在建图完成后需要我们使用DFS与BFS遍历整个图然后按照遍历的顺序输出每个连通的图的节点的值

解题思路

根据要求走就行了,建图,然后DFS和BFS//第一个完全靠自己写出来的图的题,不容易啊😭😭😭

本文使用的是邻接矩阵来表示图

在使用BFS进行遍历时,因为数据量比较小,所以只需要使用一个数组和两个作为头尾的数字就能作为队列

代码

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
#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 10

typedef struct GNode* PtrToGraph;
struct GNode
{
int E,V;//分别为边数E和顶点数V
int G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGraph MGraph;

char Visited[MaxVertexNum] = {0};//是否访问过该节点
int Q[MaxVertexNum] = {0};//用来做队列的数组
MGraph CreatGraph(int V,int E)
{//建图,初始化图的边和节点值
int i,m,n;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode));
Graph -> V = V;
Graph -> E = E;
for(i = 0;i < E;i++)
{
scanf("%d %d\n",&m,&n);
Graph->G[m][n] = 1;
Graph->G[n][m] = 1;
}
return Graph;
}

void DFS(MGraph Graph,int x)
{
Visited[x] = 1;//进入一个节点就把访问过的标记为True
printf("%d ",x);
int i;
for(i = 0;i < Graph->V;i++)
{
if((Graph->G[i][x] == 1) && (!Visited[i]))//使用DFS访问节点x相邻且没有被访问过的节点
{
DFS(Graph,i);
}
}
}
void ResetGraph(MGraph Graph)
{
for(int i = 0;i<MaxVertexNum;i++)
Visited[i] = 0;
}
void BFS(MGraph Graph,int x)
{
int i,head,rear;
head = -1;
rear = 0;
Q[0] = x;
Visited[x] = 1;//进入BFS时把BFS的入口节点视为访问过
while(head != rear)//当队列不为空
{
head++;
printf("%d ",Q[head]);//输出头结点
for(i=0;i < Graph->V;i++)
{//遍历所有节点,如果是头结点的邻接点且没有被访问过则入队
if(!Visited[i] && (Graph->G[i][Q[head]] == 1))
{
rear++;
Q[rear] = i;
Visited[i] = 1;
}
}
}
}

int main()
{
int V,E,i;
MGraph Graph;
scanf("%d %d\n",&V,&E);
Graph = CreatGraph(V,E);
for(i = 0;i < V ;i++)
{
if(!Visited[i])
{
printf("{ ");
DFS(Graph,i);
printf("}\n");
}
}
ResetGraph(Graph);
for(i = 0;i < V;i++)
{
if(!Visited[i])
{
printf("{ ");
BFS(Graph,i);
printf("}\n");
}
}
}