问题描述】根据输入的图的邻接矩阵A,判断此图的连通分量的个数, 第一行为图的结点个数n,之后的n行为邻接矩阵的内容,每行n个数表示。其中A]=1表示两个结点邻接,而A[i]=0表示两个结点无邻接关系。【输出形式】输出此图连通分量的个数。写一个c语言代码
时间: 2024-11-17 12:29:09 浏览: 80
五项连通图的遍历 C语言 数据结构
在C语言中,要计算给定邻接矩阵表示的图的连通分量个数,你可以使用深度优先搜索(DFS)或者广度优先搜索(BFS)算法。这里提供一个基于DFS的简单示例代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 100 // 图的最大节点数
// 用于表示图的邻接矩阵
bool adj[MAX_N][MAX_N];
// 邻接表辅助结构
typedef struct {
int node;
struct Node* next;
} Edge;
// 判断两个节点是否在同一连通分量
void dfs(int start, bool visited[], Edge** edges) {
visited[start] = true;
Edge* current = edges[start];
while (current != NULL) {
if (!visited[current->node]) {
dfs(current->node, visited, edges);
}
current = current->next;
}
}
// 找出所有连通分量并返回数量
int count_connected_components(int n, int adj_matrix[]) {
int components = 0;
bool visited[n + 1];
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
++components;
dfs(i, visited, edges); // 边存储在edges数组中,初始化为NULL
Edge* edge = NULL;
for (int j = 1; j <= n; j++) {
if (adj[i][j] == 1) {
edge = (Edge*)malloc(sizeof(Edge));
edge->node = j;
edge->next = NULL;
edges[i] = edge;
}
}
}
}
return components;
}
// 主函数,接受输入并输出结果
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &adj[i+1][j+1]);
}
}
Edge* edges[MAX_N]; // 初始化边缘列表
int components = count_connected_components(n, adj);
printf("图中有 %d 个连通分量.\n", components);
return 0;
}
```
注意,这个代码假设你已经将输入的邻接矩阵转换成了边的形式,并存储在`edges`数组中。如果直接给出的是邻接矩阵,你需要先将其转换成邻接表结构。
阅读全文