设具有n个顶点的有向图用邻接表存储。试写出计算所有顶点入度的算法

在一个使用邻接表表示的有向图中，每个顶点通常会有一个邻接列表，其中包含了所有指向该顶点的边。计算所有顶点的入度意味着统计有多少条边进入每个顶点。下面是一个简单的算法描述：

1. 初始化一个大小为n的数组或vector，名为`in_degrees`，用于存储每个顶点的入度。数组的索引对应于顶点编号。

2. 遍历邻接表的所有顶点（从0到n-1）：
a. 对于每个顶点v，获取其对应的邻接列表。
b. 对邻接列表中的每一个顶点u，如果u不在`in_degrees`数组中，初始化它的值为0；然后将`in_degrees[u]`加一，因为有一条从v到u的边。

3. 完成遍历后，`in_degrees`数组就包含了所有顶点的入度信息。

伪代码如下：

for i = 0 to n-1 {
    in_degrees[i] = 0;
}
foreach vertex v and its adjacency list neighbors in graph {
    for each neighbor u in neighbors {
        in_degrees[u]++;
    }
}

相关问题

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

### 回答1：
计算有向图中各顶点的入度的算法如下：

1. 初始化一个大小为n的数组indegree，其中n为图中顶点的数量，将每个元素初始化为0。

2. 遍历邻接表，对于每个顶点，遍历其所对应的边，将该边的终点顶点的入度加1。

3. 返回indegree数组，该数组中第i个元素即表示第i个顶点的入度。

以下是该算法的具体实现，假设邻接表采用链式前向星存储：

const int N = 100010;

int head[N], ver[N], nxt[N], idx;  // 链式前向星存储图
int indegree[N];                   // 存储每个顶点的入度

void add(int a, int b) {
    ver[++idx] = b;
    nxt[idx] = head[a];
    head[a] = idx;
}

void get_indegree(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; j; j = nxt[j]) {
            indegree[ver[j]]++;
        }
    }
}

其中，add函数用于向链式前向星中添加一条从a到b的边，get_indegree函数用于计算各顶点的入度。

### 回答2：
若有向图采用邻接表作为存储结构，我们可以通过遍历邻接表来计算每个顶点的入度。

算法步骤如下：
1. 创建一个长度为顶点数的数组indegree，用于记录每个顶点的入度。
2. 遍历图中每个顶点的邻接表。
3. 对于每个邻接表中的节点，将其对应的顶点的入度加一。即indegree[v] += 1，其中v为当前节点的值。
4. 遍历所有顶点，输出每个顶点的入度。

该算法的时间复杂度为O(V + E)，其中V为顶点数，E为边数。通过遍历每个节点的邻接表，我们可以快速计算出每个顶点的入度。

例如，对于以下有向图的邻接表表示：
1->2->3->5
2->4
3->5
4->3
5

根据算法步骤：
1. 创建长度为5的数组indegree。
2. 遍历每个顶点的邻接表：
- 对于顶点1，它的邻接表为2->3->5，将2、3、5的入度分别加一：indegree[2] += 1，indegree[3] += 1，indegree[5] += 1。
- 对于顶点2，它的邻接表为4，将4的入度加一：indegree[4] += 1。
- 对于顶点3，它的邻接表为5，将5的入度加一：indegree[5] += 1。
- 对于顶点4，它的邻接表为3，将3的入度加一：indegree[3] += 1。
- 对于顶点5，它没有邻接表。
3. 输出每个顶点的入度：indegree[1]为0，indegree[2]为1，indegree[3]为2，indegree[4]为1，indegree[5]为2。

2-2 设具有n个顶点的有向图用邻接表存储（不存在逆邻接表）。试写出计算所有顶点入度的算法，将每个顶点的入度值分别存入一维数组 int Indegree[n]中C语言

以下是计算所有顶点入度的算法，将每个顶点的入度值分别存入一维数组 int Indegree[n]中：

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

#define MAX_VERTEX_NUM 100

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *next;
} ArcNode;

typedef struct VNode {
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

void CreateGraph(ALGraph *G) {
    printf("请输入有向图的顶点数和边数：\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);

    printf("请输入有向图的各个顶点信息：\n");
    for (int i = 0; i < G->vexnum; i++) {
        G->vertices[i].firstarc = NULL;
    }

    printf("请输入有向图的各个边的信息：\n");
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        printf("请输入第%d条边的两个端点：\n", i + 1);
        scanf("%d%d", &v1, &v2);

        ArcNode *arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = v2;
        arc->next = G->vertices[v1].firstarc;
        G->vertices[v1].firstarc = arc;
    }
}

void ComputeIndegree(ALGraph *G, int Indegree[]) {
    for (int i = 0; i < G->vexnum; i++) {
        Indegree[i] = 0;
    }

    for (int i = 0; i < G->vexnum; i++) {
        ArcNode *arc = G->vertices[i].firstarc;
        while (arc != NULL) {
            int j = arc->adjvex;
            Indegree[j]++;
            arc = arc->next;
        }
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);

    int Indegree[MAX_VERTEX_NUM];
    ComputeIndegree(&G, Indegree);

    printf("各个顶点的入度分别为：\n");
    for (int i = 0; i < G.vexnum; i++) {
        printf("%d ", Indegree[i]);
    }
    printf("\n");

    return 0;
}