用c语言实现下列操作给定一个无向图和其中的所有边,判断这个图是否所有顶点都是连通的。 输入每组数据的第一行是两个整数 n 和 m(0<=n<=1000)。n 表示图的顶点数目,m 表示图中边的数目。如果 n 为 0 表示输入结束。随后有 m 行数据,每行有两个值 x 和 y(0<x, y <=n),表示顶点 x 和 y 相连,顶点的编号从 1 开始计算。输入不保证这些边是否重复。 对于每组输入数据,如果所有顶点都是连通的,输出"YES",否则输出"NO"。
时间: 2024-03-03 20:50:41 浏览: 95
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来判断一个图是否连通。以下是使用DFS的方法:
首先,我们需要定义一个函数dfs来遍历图中的每一个连通块。dfs的参数包括当前遍历的顶点v、已经遍历过的顶点集合visited和图的邻接表adj。
在dfs函数内部,首先将当前顶点v标记为已访问,然后遍历v的邻居节点。对于每个邻居节点u,如果u还没有被访问过,则递归调用dfs函数来遍历u所在的连通块。
最后,在主函数中,我们遍历图中的每一个顶点,如果发现某个顶点没有被访问过,则说明该顶点所在的连通块与之前遍历过的连通块不相交,因此整个图不连通,输出"NO"。如果所有顶点都被访问过,则输出"YES"。
下面是使用DFS判断图连通性的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1005
int n, m;
int adj[MAXN][MAXN];
int visited[MAXN];
void dfs(int v) {
visited[v] = 1;
for (int u = 1; u <= n; u++) {
if (adj[v][u] && !visited[u]) {
dfs(u);
}
}
}
int is_connected() {
for (int i = 1; i <= n; i++) {
visited[i] = 0;
}
dfs(1);
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
return 0;
}
}
return 1;
}
int main() {
while (scanf("%d%d", &n, &m) == 2 && n > 0) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj[i][j] = 0;
}
}
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x, &y);
adj[x][y] = adj[y][x] = 1;
}
if (is_connected()) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
```
该代码的时间复杂度为O(n^2),空间复杂度为O(n^2)。其中,邻接矩阵adj用来存储图的边,visited用来标记图中的顶点是否已经被访问过。
阅读全文