第一行输入图的结点个数n,之后输入n*n的邻接矩阵的内容,A[i][j]=1表示两个结点邻接,而A[i][j]=0表示两个结点无邻接关系。 输出此图连通分量的个数。C语言
时间: 2024-05-03 16:17:17 浏览: 76
C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列
5星 · 资源好评率100%
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来求解连通分量个数。
以下是使用DFS的解法:
```c
#include <stdio.h>
#define MAXN 100
int n;
int graph[MAXN][MAXN];
int visited[MAXN];
void dfs(int u) {
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (graph[u][v] && !visited[v]) {
dfs(v);
}
}
}
int count_components() {
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
count++;
}
}
return count;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("Number of connected components: %d\n", count_components());
return 0;
}
```
首先,读入图的邻接矩阵。然后,定义一个`visited`数组,用来标记每个结点是否被访问过。接着,从每个未被访问过的结点开始,调用`dfs`函数进行深度优先搜索,并增加计数器`count`的值。最后,输出`count`的值即为连通分量的个数。
注意,为了防止递归调用`dfs`函数时出现栈溢出,可以设置系统栈的大小,例如:
```c
#include <stdlib.h>
#include <sys/resource.h>
int main() {
struct rlimit limit;
getrlimit(RLIMIT_STACK, &limit);
limit.rlim_cur = 1024 * 1024;
setrlimit(RLIMIT_STACK, &limit);
/* ... */
return 0;
}
```
其中,`getrlimit`和`setrlimit`函数用来获取和设置系统资源的限制,`RLIMIT_STACK`表示栈的大小限制,单位是字节。上述代码将栈的大小限制设置为1MB。
阅读全文