根据输入的图的邻接矩阵A,判断此图的连通分量的个数。c语言实现
时间: 2023-11-16 09:23:39 浏览: 102
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)遍历图的所有节点,统计连通分量的个数。以下是使用DFS实现的代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAXN 100
int n; // 图的节点数
int A[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 标记节点是否已被访问
void dfs(int u) {
visited[u] = true;
for (int v = 0; v < n; v++) {
if (A[u][v] && !visited[v]) {
dfs(v);
}
}
}
int count_components() {
int cnt = 0;
for (int u = 0; u < n; u++) {
if (!visited[u]) {
cnt++;
dfs(u);
}
}
return cnt;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &A[i][j]);
}
}
int cnt = count_components();
printf("The number of connected components is %d\n", cnt);
return 0;
}
```
其中,dfs函数表示从节点u开始进行深度优先遍历,visited数组用于标记节点是否已被访问过。count_components函数遍历所有未访问过的节点,每次遍历都会发现一个新的连通分量,最终返回连通分量的个数。
阅读全文