用代码计算有向图的各顶点的入度

假设有向图用邻接矩阵表示，其中 n 个顶点的编号为 0 到 n-1，则可以通过以下代码计算每个顶点的入度：

# 假设图用邻接矩阵表示，matrix[i][j] 表示从顶点 i 到顶点 j 是否有一条有向边
# n 表示顶点数
def calc_indegrees(matrix, n):
    indegrees = [0] * n
    for i in range(n):
        for j in range(n):
            if matrix[i][j]:
                indegrees[j] += 1
    return indegrees

上述代码的时间复杂度为 O(n^2)，可以通过优化邻接矩阵表示方式或者使用邻接表等数据结构来进一步优化时间复杂度。

相关问题

用c语言代码算求有向图每个顶点的入度和出度

以下是用C语言计算有向图每个顶点的入度和出度的代码示例：

#include <stdio.h>

#define MAX_VERTICES 100 // 最大顶点数

// 有向图的邻接矩阵表示法
typedef struct {
    int n; // 顶点数
    int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
} Graph;

// 计算有向图每个顶点的入度和出度
void calc_degrees(Graph* g, int* in_degrees, int* out_degrees) {
    int i, j;
    for (i = 0; i < g->n; i++) {
        in_degrees[i] = 0; // 初始化入度为0
        out_degrees[i] = 0; // 初始化出度为0
        for (j = 0; j < g->n; j++) {
            if (g->adj[i][j] != 0) {
                out_degrees[i]++; // 计算出度
                in_degrees[j]++; // 计算入度
            }
        }
    }
}

int main() {
    Graph g = {5, {{0, 1, 0, 0, 1},
                   {0, 0, 1, 0, 0},
                   {0, 0, 0, 1, 1},
                   {0, 0, 0, 0, 1},
                   {0, 0, 0, 0, 0}}}; // 有向图的邻接矩阵表示法
    int in_degrees[MAX_VERTICES], out_degrees[MAX_VERTICES]; // 存储每个顶点的入度和出度
    int i;

    calc_degrees(&g, in_degrees, out_degrees); // 计算每个顶点的入度和出度

    printf("顶点\t入度\t出度\n");
    for (i = 0; i < g.n; i++) {
        printf("%d\t%d\t%d\n", i, in_degrees[i], out_degrees[i]);
    }

    return 0;
}

以上代码中，我们先定义了一个 `Graph` 结构体来表示有向图的邻接矩阵表示法。然后，我们通过 `calc_degrees` 函数计算每个顶点的入度和出度。最后，我们输出每个顶点的入度和出度。

若有向图采用邻接表作为存储结构，试给出计算图中各顶点的入度的算法。

### 回答1：
对于采用邻接表作为存储结构的有向图，计算每个顶点的入度可以采用以下算法：

1. 初始化每个顶点的入度为0。

2. 遍历邻接表中的每个节点，将该节点所指向的顶点的入度加1。

3. 遍历完所有节点后，每个顶点的入度即为其累加的入度值。

例如，对于以下有向图的邻接表：

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

计算各顶点的入度的算法如下：

1. 初始化每个顶点的入度为0。

2. 遍历邻接表中的每个节点，将该节点所指向的顶点的入度加1。具体操作如下：

- 节点0指向顶点1和2，因此顶点1和2的入度均加1。
- 节点1指向顶点3，因此顶点3的入度加1。
- 节点2指向顶点1，因此顶点1的入度加1。
- 节点3指向顶点2，因此顶点2的入度加1。

3. 遍历完所有节点后，每个顶点的入度即为其累加的入度值。因此，该有向图中各顶点的入度分别为：

顶点0的入度为0
顶点1的入度为2
顶点2的入度为2
顶点3的入度为2

### 回答2：
邻接表是一种表示图的数据结构，其中每个顶点都对应一条链表，链表中存储了该顶点与其他顶点相连的所有边。邻接表在图的遍历和查询操作中具有较好的时间复杂度。为计算有向图中各顶点的入度，可以遍历邻接表，统计每个节点被其他节点指向的次数。

具体算法如下：

1. 初始化一个长度为N的数组inDegree，其中N为图中节点的个数，数组中每个元素初始化为0。

2. 遍历邻接表中所有顶点及其相邻的边，对于每条边(x, y)，将y节点的入度加1。具体实现方式为：在x节点的链表中查找y节点的位置，若存在，则在inDegree数组中将y节点的入度加1。

3. 遍历完所有边之后，inDegree数组中存储了每个节点的入度值，输出数组即可。

该算法的时间复杂度为O(E)，其中E表示图中边的数量，因为要遍历每一条边，才能统计每个节点的入度。空间复杂度为O(N)，因为需要创建一个长度为N的数组来存储每个节点的入度值。

总之，在有向图中，入度表示指向该节点的所有边的数量，通过使用邻接表来存储图，我们可以轻松地统计每个节点的入度，并使用该信息进行后续操作。

### 回答3：
邻接表是一种常用的有向图的存储结构，它通过链式结构将图中每个顶点以及与之相邻的顶点都存储在一个单独的链表中。

计算有向图中各顶点的入度，我们可以遍历整个邻接表，对每个顶点的入度进行计数。具体步骤如下：

1. 初始化每个顶点的入度为0。

2. 遍历邻接表，对于每个顶点v，在其相邻的链表中统计每个顶点u出现次数，即u的入度加一。

3. 输出每个顶点的入度。

代码示例：

def calc_indegree(adj_list):
    n = len(adj_list) # 图中顶点数目
    indegree = [0] * n # 初始化每个顶点的入度为0
    
    # 遍历每个顶点的相邻链表
    for v in range(n):
        cur = adj_list[v].head
        while cur is not None:
            indegree[cur.data] += 1 # 对每个相邻的顶点的入度加一
            cur = cur.next
            
    # 输出每个顶点的入度
    for i in range(n):
        print('Vertex %d has indegree %d' % (i, indegree[i]))

以上算法的时间复杂度为O(E+V)，其中E为图中边的数目，V为图中顶点的数目。在邻接表表示法中，E和V的大小一般相差不大，因此该算法的时间复杂度可以视为O(V)。