c语言) 键盘输入数据,建立一个有向图的邻接表。 (2) 输出该邻接表。 (3) 在有向图的邻接表的基础上计算各顶点的度,并输出
时间: 2024-03-03 09:51:14 浏览: 74
有向图的邻接表(C语言)
好的,让我给你提供一个 C 语言实现的代码,来完成你的要求。
首先,我们假设输入数据的格式如下:
```
5 6
1 2
1 3
2 3
2 4
3 4
4 5
```
其中第一行的两个数字表示顶点数和边数,接下来的每一行表示一条边。
那么我们可以使用 C 语言来实现建立邻接表的过程,代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100005
struct Edge {
int v;
struct Edge* next;
};
struct Edge* head[MAXN];
int out_degree[MAXN];
int in_degree[MAXN];
void add_edge(int u, int v) {
struct Edge* p = (struct Edge*) malloc(sizeof(struct Edge));
p->v = v;
p->next = head[u];
head[u] = p;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
// 初始化邻接表
for (int i = 1; i <= n; i++) {
head[i] = NULL;
out_degree[i] = 0;
in_degree[i] = 0;
}
// 添加边
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
}
// 输出邻接表
for (int i = 1; i <= n; i++) {
printf("%d: ", i);
for (struct Edge* p = head[i]; p != NULL; p = p->next) {
printf("%d ", p->v);
}
printf("\n");
}
// 计算各顶点的度
for (int i = 1; i <= n; i++) {
out_degree[i] = 0;
in_degree[i] = 0;
for (struct Edge* p = head[i]; p != NULL; p = p->next) {
out_degree[i]++;
in_degree[p->v]++;
}
}
// 输出各顶点的度
for (int i = 1; i <= n; i++) {
printf("顶点 %d 的度为:出度 %d,入度 %d\n", i, out_degree[i], in_degree[i]);
}
return 0;
}
```
这样,我们就完成了建立有向图的邻接表、输出邻接表和计算各顶点的度的过程。
阅读全文