c语言实现一个函数,统计无向图中边的个数
时间: 2024-03-02 20:50:14 浏览: 76
可以使用邻接表来存储无向图,然后遍历每个顶点的邻居节点并计数,最后将所有顶点的度数相加再除以2即为边的个数。
以下是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
struct node {
int val;
struct node *next;
};
struct node *create_node(int val) {
struct node *new_node = (struct node*)malloc(sizeof(struct node));
new_node->val = val;
new_node->next = NULL;
return new_node;
}
void add_edge(struct node *adj_list[], int u, int v) {
struct node *new_node = create_node(v);
new_node->next = adj_list[u];
adj_list[u] = new_node;
new_node = create_node(u);
new_node->next = adj_list[v];
adj_list[v] = new_node;
}
int count_edges(struct node *adj_list[], int n) {
int degree_sum = 0;
for (int i = 1; i <= n; i++) {
struct node *curr = adj_list[i];
while (curr != NULL) {
degree_sum++;
curr = curr->next;
}
}
return degree_sum / 2;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
struct node *adj_list[MAX_N + 1] = {NULL};
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(adj_list, u, v);
}
int edge_count = count_edges(adj_list, n);
printf("%d\n", edge_count);
return 0;
}
```
其中,`n` 表示顶点个数,`m` 表示边的个数,`adj_list` 存储了每个顶点的邻居节点。遍历邻接表并计算每个顶点的度数,最后将度数相加再除以2即为边的个数。
阅读全文