假设不带权有向图采用邻接表 G 存储，下面算法的功能是：求出图中每个顶点的入度。 请在空白处填入正确的语句。 //求出图 G 中每个顶点的入度void InDs(ALGraph *G) { ArcNode *p; //A 存放各顶点的入度 int A[MAX_VERTEX_NUM], i; //A 中元素置初值 0 for(i = 0; i<G->n; i++) A[i]=0; for(i = 0; i < G->n; i++) { //扫描所有头结点 p = ____________; while(p != NULL) { //扫描边结点 ____________; //表示 i 到 p->adjvex 顶点有一条边 p = p->nextarc; } } printf("各顶点入度:\n"); //输出各顶点的入度 for(i = 0; i < G->n; i++) printf(" 顶点%d:%d\n", i, A[i]); }

空白处填写的语句是：

p = G->vertices[i].firstarc;
A[p->adjvex]++;

第一个循环已经将 A 数组初始化为 0。

第二个循环是为了遍历图中的每个顶点，对于每个顶点，访问其邻接表中的边结点来更新其入度。

在处理每个头结点时，我们需要通过 `p = G->vertices[i].firstarc` 获取其邻接表的第一个边结点。

然后，我们需要遍历该顶点的所有出边，即遍历该顶点的邻接表，对于每个邻接点，通过 `p->adjvex` 获取其顶点号，然后将该顶点的入度加 1，即 `A[p->adjvex]++`。

这样，我们就可以求出图中每个顶点的入度了。

相关问题

假设不带权有向图采用邻接表g存储，设计算法输出顶点i的所有入边邻接点。

算法步骤如下：

1. 遍历邻接表g，找到所有以顶点i为终点的边。

2. 对于每条以顶点i为终点的边，记录其起点。

3. 输出所有记录的起点，即为顶点i的所有入边邻接点。

具体实现可以使用一个数组来记录每个顶点的入度，遍历邻接表时将每条边的起点入度加1，最后遍历入度数组，输出所有入度为1的顶点即可。

假设有向图g采用邻接表存储，设计一个算法求出图g每个顶点的入度

可以遍历邻接表中的每个顶点，并统计每个顶点的入度。具体地，可以定义一个数组in_degree，初始值都为0，然后遍历邻接表，对于每个顶点v的邻接表中的每个顶点u，都将in_degree[u]增加1。最终in_degree数组中的每个元素即为对应顶点的入度。

以下是具体的算法实现：

def get_in_degree(adj_list):
    n = len(adj_list)
    in_degree = [0] * n
    for u in range(n):
        for v in adj_list[u]:
            in_degree[v] += 1
    return in_degree

其中，adj_list是邻接表，n是顶点数。算法的时间复杂度是O(m+n)，其中m是边数。