已知有一个有向图的邻接表,试用C语言编写一个算法,计算各顶点的入度,输出运行结果
时间: 2024-01-24 22:17:01 浏览: 115
以下是计算各顶点入度的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
/* 邻接表中的边结构体 */
typedef struct EdgeNode {
int adjvex; // 相邻节点编号
struct EdgeNode* next_edge; // 下一个边结点指针
} EdgeNode;
/* 邻接表中的顶点结构体 */
typedef struct VertexNode {
int vertex; // 顶点编号
EdgeNode* first_edge; // 第一个边结点指针
} VertexNode;
/* 邻接表结构体 */
typedef struct AdjList {
VertexNode vertices[MAX_VERTICES]; // 顶点数组
int num_vertices; // 顶点数
} AdjList;
/* 初始化邻接表 */
void init_adj_list(AdjList* adj_list) {
int i;
adj_list->num_vertices = 0;
for (i = 0; i < MAX_VERTICES; i++) {
adj_list->vertices[i].first_edge = NULL;
}
}
/* 向邻接表中插入一条边 */
void insert_edge(AdjList* adj_list, int from_vertex, int to_vertex) {
EdgeNode* new_edge = (EdgeNode*)malloc(sizeof(EdgeNode));
new_edge->adjvex = to_vertex;
new_edge->next_edge = adj_list->vertices[from_vertex].first_edge;
adj_list->vertices[from_vertex].first_edge = new_edge;
}
/* 计算各顶点入度 */
void calc_indegree(AdjList* adj_list, int* indegrees) {
int i;
EdgeNode* cur_edge;
for (i = 0; i < adj_list->num_vertices; i++) {
indegrees[i] = 0; // 初始化入度为0
}
for (i = 0; i < adj_list->num_vertices; i++) {
cur_edge = adj_list->vertices[i].first_edge;
while (cur_edge != NULL) {
indegrees[cur_edge->adjvex]++; // 计算入度
cur_edge = cur_edge->next_edge;
}
}
}
/* 主函数 */
int main() {
AdjList adj_list;
int indegrees[MAX_VERTICES];
int i;
init_adj_list(&adj_list);
// 向邻接表中插入边
insert_edge(&adj_list, 0, 1);
insert_edge(&adj_list, 0, 2);
insert_edge(&adj_list, 1, 2);
insert_edge(&adj_list, 2, 0);
insert_edge(&adj_list, 2, 3);
insert_edge(&adj_list, 3, 3);
// 计算各顶点入度
calc_indegree(&adj_list, indegrees);
// 输出各顶点入度
for (i = 0; i < adj_list.num_vertices; i++) {
printf("Vertex %d indegree: %d\n", i, indegrees[i]);
}
return 0;
}
```
以上代码中,我们首先定义了邻接表的数据结构,并实现了初始化邻接表和向邻接表中插入一条边的函数。然后,我们实现了计算各顶点入度的函数,并在主函数中调用这个函数计算各顶点入度并输出结果。
阅读全文