已知有一个有向图的邻接表，试编写一个算法，计算各顶点的入度。的代码

假设邻接表中有 $n$ 个节点，我们可以使用一个长度为 $n$ 的数组来记录每个节点的入度。算法的具体步骤如下：

1. 初始化每个节点的入度为 0。
2. 遍历邻接表中的每个节点，对于每个节点的邻接链表中的每个节点，将其对应的节点的入度加 1。
3. 返回记录每个节点入度的数组。

下面是具体的实现代码：

def compute_indegree(adj_list):
    n = len(adj_list)
    indegrees = [0] * n
    for node in adj_list:
        for neighbor in adj_list[node]:
            indegrees[neighbor] += 1
    return indegrees

其中 `adj_list` 是邻接表，它是一个字典，键为节点编号，值为一个列表，表示该节点的邻接链表。返回值 `indegrees` 是一个列表，表示每个节点的入度。

相关问题

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

算法步骤如下：

1. 初始化一个数组 inDegree，长度为顶点数，全部初始化为0。

2. 遍历邻接表，对于每个链表中的节点，将节点指向的顶点的入度加1，即：inDegree[v]++，其中 v 是节点指向的顶点。

3. 遍历 inDegree 数组，输出每个顶点的入度。

下面是 Python 代码实现：

def calc_indegree(adj_list):
    # 初始化入度数组
    num_vertices = len(adj_list)
    in_degree = [0] * num_vertices

    # 遍历邻接表，计算入度
    for edges in adj_list:
        for v in edges:
            in_degree[v] += 1

    # 输出入度
    for i in range(num_vertices):
        print(f"Vertex {i} has in-degree {in_degree[i]}")

# 示例代码
adj_list = [[1, 2], [2], [3], [], [1, 2]]
calc_indegree(adj_list)

输出结果为：

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

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

0 -> 1 -> 2
1 -> 2
2 -> 3
3 ->
4 -> 1 -> 2

求邻接表表示的有向图各顶点的入度 正文: 已知有一个有向图的邻接表，试编写一个算法，计算各顶点的入度。用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