求邻接表表示的有向图各顶点的入度 正文: 已知有一个有向图的邻接表，试编写一个算法，计算各顶点的入度。用C语言实现

下面是用 C 语言实现计算有向图各顶点入度的算法，假设邻接表用一个指针数组来表示，每个指针指向一个链表，链表中存储该顶点指向的其他顶点。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// 邻接表中的链表节点
typedef struct Node {
    int dest;           // 目标顶点编号
    struct Node* next;  // 链表中的下一个节点
} Node;

// 邻接表中的顶点
typedef struct Vertex {
    Node* head;         // 链表头指针
    int in_degree;      // 顶点入度
} Vertex;

// 邻接表表示的有向图
typedef struct Graph {
    Vertex vertices[MAX_VERTICES];  // 顶点数组
    int num_vertices;               // 顶点数
} Graph;

// 初始化有向图
void init_graph(Graph* graph, int num_vertices) {
    graph->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++) {
        graph->vertices[i].head = NULL;
        graph->vertices[i].in_degree = 0;
    }
}

// 添加有向边
void add_edge(Graph* graph, int src, int dest) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->dest = dest;
    new_node->next = graph->vertices[src].head;
    graph->vertices[src].head = new_node;

    graph->vertices[dest].in_degree++;
}

// 计算各顶点的入度
void calc_in_degree(Graph* graph) {
    for (int i = 0; i < graph->num_vertices; i++) {
        Node* p = graph->vertices[i].head;
        while (p != NULL) {
            graph->vertices[p->dest].in_degree++;
            p = p->next;
        }
    }
}

// 打印各顶点的入度
void print_in_degree(Graph* graph) {
    for (int i = 0; i < graph->num_vertices; i++) {
        printf("Vertex %d has in-degree %d\n", i, graph->vertices[i].in_degree);
    }
}

// 测试代码
int main() {
    Graph graph;
    init_graph(&graph, 5);
    add_edge(&graph, 0, 1);
    add_edge(&graph, 0, 2);
    add_edge(&graph, 1, 2);
    add_edge(&graph, 2, 3);
    add_edge(&graph, 4, 1);
    add_edge(&graph, 4, 2);

    calc_in_degree(&graph);
    print_in_degree(&graph);

    return 0;
}

输出结果为：

Vertex 0 has in-degree 0
Vertex 1 has in-degree 2
Vertex 2 has in-degree 3
Vertex 3 has in-degree 1
Vertex 4 has in-degree 0

其中，邻接表表示的有向图如下所示：

0 -> 1 -> 2
    |
    v
    2 -> 3
4 -> 1 -> 2