设有向无权图G用邻接矩阵存储，设计一个算法求出图G中每个顶点的入度（数据结构作业）

对于给定的无权图G，其邻接矩阵是一个二维数组，其中行表示源顶点，列表示目标顶点。如果元素值为1，则表示从源顶点到目标顶点有一条边；如果为0，则表示没有边。为了计算每个顶点的入度，即指向它的边的数量，我们可以按照以下步骤设计算法：

1. 初始化一个长度为V（顶点数）的数组inDegree，将所有值初始化为0。这将用于存储每个顶点的入度。

2. 遍历邻接矩阵A，对于每一行i（代表顶点i），检查列（对应其他顶点j）的非零元素。对于每个非零值，说明顶点i有一条指向顶点j的边，因此inDegree[i]加一。

3. 当遍历完邻接矩阵后，inDegree数组中的每一个元素就是对应顶点的入度。

以下是伪代码的形式表示这个算法：

function calculateInDegrees(A):
    V = number_of_vertices(A)
    inDegree = [0] * V

    for i in range(V):
        for j in range(V):
            if A[i][j] == 1:  // 如果矩阵中有边连接i和j
                inDegree[i] += 1  // 更新顶点i的入度

    return inDegree

相关问题

假设不带权有向图采用邻接表 G 存储，设计实现以下功能的算法： (1）求出图中每个顶点的入度。 (2）求出图中每个顶点的出度。 (3）求出图中出度为0的顶点数。

对于无权有向图的邻接表存储结构，我们可以设计如下的算法来实现这些功能：

(1) 求出图中每个顶点的入度：
- 对于每一个顶点 v，遍历其邻接表，每遇到一条指向 v 的边，就将对应的源节点的入度加一。因为邻接表通常是键值对的形式，键代表目标顶点，值是一个列表，包含了所有指向这个目标的边。所以可以在遍历时累加每个边的源节点的入度计数。

def in_degree(G, vertex):
    count = 0
    for neighbor in G[vertex]:
        count += 1
    return count

# 遍历所有顶点计算入度
in_degrees = {v: in_degree(G, v) for v in G}

(2) 求出图中每个顶点的出度：
- 类似地，遍历每个顶点的邻接表，但是这次统计的是有多少条边从该顶点出发。

def out_degree(G, vertex):
    count = len(G[vertex])  # 由于邻接表每个元素对应一条边
    return count

out_degrees = {v: out_degree(G, v) for v in G}

(3) 求出图中出度为0的顶点数：
- 只需遍历 `out_degrees` 字典，统计出度为 0 的顶点即可。

isolated_vertices = [v for v, degree in out_degrees.items() if degree == 0]
number_of_isolated = len(isolated_vertices)

C语言编写程序：假设不带权有向图采用邻接表 G 存储，设计实现以下功能的算法： (1）求出图中每个顶点的入度。 (2）求出图中每个顶点的出度。 (3）求出图中出度为0的顶点数

在C语言中，为了实现对无权有向图的邻接表表示，我们可以创建两个数组，一个用于存储顶点的邻接节点列表，另一个用于存储每个顶点的入度或出度。以下是针对所给功能的简单算法：

(1) 求出图中每个顶点的入度：

int* in_degrees; // 初始化为图中所有顶点的大小
void compute_in_degrees(graph* G, int num_vertices) {
    for (int i = 0; i < num_vertices; i++) {
        in_degrees[i] = 0;
        for (int j = 0; j < G[i].size(); j++) { // 遍历邻接节点列表
            in_degrees[G[i][j]]++; // 对每个相邻顶点的入度加一
        }
    }
}

(2) 求出图中每个顶点的出度：

int* out_degrees; // 初始化为图中所有顶点的大小
void compute_out_degrees(graph* G, int num_vertices) {
    out_degrees = malloc(sizeof(int) * num_vertices); // 动态分配内存
    for (int i = 0; i < num_vertices; i++) {
        out_degrees[i] = 0;
        for (int adj_vertex : G[i]) { // 遍历当前顶点的所有邻居
            out_degrees[adj_vertex]++;
        }
    }
    free(out_degrees); // 释放内存
}

(3) 求出图中出度为0的顶点数：

int count_vertices_with_zero_out_degree(graph* G, int num_vertices) {
    int zero_out_vertices = 0;
    for (int i = 0; i < num_vertices; i++) {
        if (out_degrees[i] == 0)
            zero_out_vertices++;
    }
    return zero_out_vertices;
}