编程题7-6-列出连通集
【编程题】7-6 列出连通集
1 题目原文
题目链接：
给定一个有
n n
n 个顶点和
m m
m
条边的无向图，请用深度优先遍历（
DFS
）和广度优先遍历（
BFS
）分别列出其所有的连通集。假设顶点从
0 0
0 到
n − 1 n−1
n
−
1 编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第
1 1
1 行给出
2 2
2 个整数
n ( 0 < n ≤ 10 ) n (0<n≤10)
n
(
0
<
n
≤
10
) 和
m m
m ，分别是图的顶点数和边数。随后
m m
m 行，每行给出一条边的两个端点。每行中的数字之间用
1 1
1 空格分隔。
输出格式:
按照"
{ v 1 v 2 . . . v k } { v_1 v_2… v_k}
{
v
1
v
2
…
v
k
} “的格式，每行输出一个连通集。先输出
DFS的结果，再输出BFS的结果。
输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }2 思路解析
此题考查图的
DFS
和
BFS
遍历。
针对某个结点，我们除了要知道它是属于哪个连通块以外，还要能判断它是否已经被遍历过，然后从小编号的结点到大编号的结点依次遍历，如果当前结点已经被遍历过，则跳过，否则从这个结点开始进行
DFS
和
BFS
遍历。
2.1 图的存储
一般来说，常用的图的存储方式有
邻接矩阵
和
邻接表
两种，在图的遍历中，一般选择后者存储，不过当图的结点比较少时，选择前者代码更简单。这里我们选择以
邻接矩阵
的方式存图（题目所给的
n
不超过
10
，很小，更重要的原因是题目要求结点按从小到大的顺序遍历，邻接表不好控制这个）。
2.2 DFS
给你一个结点编号
i
表示要从
i
开始遍历，除此之外你还需要知道邻接矩阵和标记数组等信息，才能完成遍历，由此可得出如下算法步骤：
输出
i；遍历当前结点
i的所有邻接结点j：
2.1 如果
j
已经被遍历过则跳过
j
，否则标记
j
，表示
j
现在已经被遍历了，然后以
j
为起点再进行
DFS
遍历。
2.3 BFS
给你一个结点编号
i
表示要从
i
开始遍历，除此之外你还需要知道邻接矩阵和标记数组等信息，同时还需要借助队列作为辅助才能完成遍历，由此可得出如下算法步骤：
判断
i是否被遍历，如果没有被遍历，则标记并将其加入队列q；如果队列不为空，循环：
2.1 取出队首元素
j
，输出
j
；
2.2 将
j
的所有未被遍历的邻接结点都加入队列，并标记。
队列的实现可以参考 ，此题的代码实现并没有使用单独的队列数据结构，而是怎么方便怎么来，具体见代码。
3 代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/** dfs 遍历 **/
void dfs(int **mat, int i, int *vis, int n) {
printf("%d ", i);
for (int j = 0; j < n; j++) {
if (mat[i][j] && !vis[j]) {
vis[j] = 1;
dfs(mat, j, vis, n);
}
}
}
void init_arr(void *arr, int n) { memset(arr, 0, n * sizeof(int)); }
int main(void) {
int n = 0, m = 0, i = 0, j = 0, u = 0, v = 0;
scanf("%d%d", &n, &m);
int **mat = (int **)malloc(n * sizeof(int *));
for (i = 0; i < n; i++) {
mat[i] = (int *)malloc(n * sizeof(int));
for (j = 0; j < n; j++) {
mat[i][j] = 0;
}
}
for (i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
mat[u][v] = mat[v][u] = 1;
}
int *vis = (int *)malloc(n * sizeof(int));
init_arr(vis, n);
for (i = 0; i < n; i++) {
if (!vis[i]) {
vis[i] = 1;
printf("{ ");
dfs(mat, i, vis, n);
printf("}\n");
}
}
/** bfs 遍历 **/
int *q = (int *)malloc((n + 1) * sizeof(int));
int k = 0;
init_arr(vis, n);
for (i = 0; i < n; i++) {
if (!vis[i]) {
vis[i] = 1;
u = v = 0;
printf("{ ");
q[v++] = i;
while (u != v) {
j = q[u++];
printf("%d ", j);
for (k = 0; k < n; k++) {
if (mat[j][k] && !vis[k]) {
vis[k] = 1;
q[v++] = k;
}
}
}
printf("}\n");
}
}
/** 销毁 **/
for (i = 0; i < n; i++) {
free(mat[i]);
}
free(mat);
free(vis);
free(q);
return 0;
}