有一个邻接表存储的图G,用c语言分别设计实现以下要求的算法:求出图中每个顶点的出度;计算图中出度为0的顶点数。完整代码
时间: 2024-02-27 11:55:10 浏览: 62
以下是求出图中每个顶点的出度和计算出度为0的顶点数的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 邻接表存储的图结构体
typedef struct ArcNode {
int adjvex; // 邻接点下标
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化邻接表存储的图
void initGraph(ALGraph *G) {
int i, j, k;
ArcNode *p;
printf("请输入图的顶点数和边数:\n");
scanf("%d %d", &G->vexnum, &G->arcnum);
printf("请输入%d个顶点的值:\n", G->vexnum);
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入%d条边的两个端点:\n", G->arcnum);
for (k = 0; k < G->arcnum; k++) {
scanf("%d %d", &i, &j);
// 添加一条边(i, j)
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
}
}
// 求出每个顶点的出度
void outDegree(ALGraph *G, int degree[]) {
int i;
ArcNode *p;
// 初始化degree数组
for (i = 0; i < G->vexnum; i++) {
degree[i] = 0;
}
// 遍历每个顶点的邻接点
for (i = 0; i < G->vexnum; i++) {
p = G->vertices[i].firstarc;
while (p != NULL) {
degree[i]++;
p = p->next;
}
}
// 输出每个顶点的出度
printf("每个顶点的出度分别为:\n");
for (i = 0; i < G->vexnum; i++) {
printf("顶点%d的出度为%d\n", i, degree[i]);
}
}
// 计算出度为0的顶点数
int zeroOutDegree(ALGraph *G) {
int i, count = 0;
ArcNode *p;
// 遍历每个顶点的出度
for (i = 0; i < G->vexnum; i++) {
p = G->vertices[i].firstarc;
if (p == NULL) { // 该顶点出度为0
count++;
}
}
return count;
}
int main() {
ALGraph G;
int degree[MAX_VERTEX_NUM];
int zeroCount;
initGraph(&G);
outDegree(&G, degree);
zeroCount = zeroOutDegree(&G);
printf("出度为0的顶点数为:%d\n", zeroCount);
return 0;
}
```
该代码实现了邻接表存储的图结构体,并且包含了求出每个顶点的出度和计算出度为0的顶点数的两个算法。其中,`outDegree`函数用于求出每个顶点的出度,`zeroOutDegree`函数用于计算出度为0的顶点数。在主函数中,先初始化邻接表存储的图,然后调用`outDegree`函数求出每个顶点的出度,并调用`zeroOutDegree`函数计算出度为0的顶点数。
阅读全文