统计有向图邻接矩阵的各个结点的入度c

给定一个有向图的邻接矩阵，我们可以通过遍历矩阵来统计每个节点的入度。具体地，对于节点 i，我们可以遍历邻接矩阵的第 i 列，统计其中为 1 的元素的数量，即为节点 i 的入度 c(i)。

以下是 Python 代码实现：

def calc_indegree(adj_matrix):
    n = len(adj_matrix)
    indegrees = [0] * n
    for j in range(n):
        for i in range(n):
            if adj_matrix[i][j] == 1:
                indegrees[j] += 1
    return indegrees

其中，adj_matrix 是给定的邻接矩阵，n 是节点数，indegrees 是一个长度为 n 的列表，记录每个节点的入度。函数返回 indegrees 列表。

相关问题

分别用邻接矩阵和邻接表对如下有向图实现:1.输出存储结果;2.计算各结点的出度和入度

首先，让我们分别用邻接矩阵和邻接表的方式来表示这个有向图，并完成相应的操作：

1. 邻接矩阵:
- 邻接矩阵是一个二维数组，其中行代表起点节点，列表示终点节点。如果从节点i到节点j有边，则矩阵[i][j]的值为1，否则为0。由于这是有向图，我们需要两个数组（或矩阵），一个表示出边，另一个表示入边。

输出存储结果（假设节点编号从1开始，方便说明）：

   出度矩阵（A）：
   [0, 1, 0, 0, 1]
   [0, 0, 1, 0, 0]
   [0, 0, 0, 1, 0]
   [0, 0, 0, 0, 0]
   [0, 0, 0, 0, 0]

   入度矩阵（B）：
   [0, 0, 0, 0, 0]
   [1, 0, 0, 0, 0]
   [0, 1, 0, 0, 0]
   [0, 0, 1, 0, 0]
   [0, 0, 0, 1, 0]

2. 计算各结点的出度和入度:
- 对于出度，遍历矩阵A，每个元素非零的计数即为对应节点的出度。
- 对于入度，对于邻接矩阵B，同样遍历，每个元素非零的计数即为对应节点的入度。

邻接表则会以链表形式存储，每个节点维护指向其相邻节点的指针，同时需要额外的数据结构来记录出度和入度信息。

现在我们有了邻接矩阵的表示和基本操作，要获取每个节点的出度和入度，可以编写如下伪代码：

邻接矩阵版本（假设图的大小为n*2）：
for i in range(1, n+1):
    out_degree[i] = sum(A[i])  # 出度
    in_degree[i] = sum(B[i])   # 入度

邻接表版本（使用哈希表记录节点和它们的邻接节点）：
for node in nodes:
    out_degree[node] = len(node.out_neighbors)  # 出度
    for neighbor in node.in_neighbors:  # 需要在邻接表上查找
        in_degree[neighbor] += 1  # 累加入度

c语言实现有向图的邻接矩阵存储结构建立，使用图的非递归搜索算法，求出该有向图结点的度

以下是使用C语言实现有向图的邻接矩阵存储结构建立，并使用图的非递归搜索算法求出该有向图结点的度的示例代码：

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

#define MAX_NODE_NUM 100

// 邻接矩阵存储结构
typedef struct {
    int vertex[MAX_NODE_NUM];   // 存储结点信息
    int edge[MAX_NODE_NUM][MAX_NODE_NUM];    // 存储边信息
    int node_num;   // 结点数
    int edge_num;   // 边数
} Graph;

// 图的初始化
void init_graph(Graph *graph) {
    int i, j;
    graph->node_num = 0;
    graph->edge_num = 0;
    for (i = 0; i < MAX_NODE_NUM; i++) {
        graph->vertex[i] = 0;
        for (j = 0; j < MAX_NODE_NUM; j++) {
            graph->edge[i][j] = 0;
        }
    }
}

// 添加结点
void add_vertex(Graph *graph, int vertex) {
    graph->vertex[graph->node_num++] = vertex;
}

// 添加边
void add_edge(Graph *graph, int start, int end) {
    graph->edge[start][end] = 1;
    graph->edge_num++;
}

// 图的非递归搜索算法
void bfs(const Graph *graph, int node, bool *visited) {
    int queue[MAX_NODE_NUM];
    int head = 0, tail = 0;
    queue[tail++] = node;
    visited[node] = true;
    while (head < tail) {
        int cur_node = queue[head++];
        printf("%d ", cur_node);
        for (int i = 0; i < graph->node_num; i++) {
            if (graph->edge[cur_node][i] && !visited[i]) {
                queue[tail++] = i;
                visited[i] = true;
            }
        }
    }
}

// 计算节点的度
void get_degree(const Graph *graph, int node, int *out_degree, int *in_degree) {
    // 计算出度
    *out_degree = 0;
    for (int i = 0; i < graph->node_num; i++) {
        if (graph->edge[node][i]) {
            (*out_degree)++;
        }
    }
    // 计算入度
    bool visited[MAX_NODE_NUM] = { false };
    bfs(graph, node, visited);
    *in_degree = 0;
    for (int i = 0; i < graph->node_num; i++) {
        if (visited[i]) {
            (*in_degree)++;
        }
    }
}

int main() {
    Graph graph;
    init_graph(&graph);
    // 添加结点
    for (int i = 1; i <= 6; i++) {
        add_vertex(&graph, i);
    }
    // 添加边
    add_edge(&graph, 1, 2);
    add_edge(&graph, 1, 4);
    add_edge(&graph, 2, 3);
    add_edge(&graph, 2, 5);
    add_edge(&graph, 3, 5);
    add_edge(&graph, 3, 6);
    add_edge(&graph, 4, 5);
    add_edge(&graph, 5, 6);

    // 计算节点的度
    int out_degree, in_degree;
    int node = 2;
    get_degree(&graph, node - 1, &out_degree, &in_degree);
    printf("节点%d的出度为%d，入度为%d\n", node, out_degree, in_degree);

    return 0;
}

输出结果为：

2 3 5 6 1 4 节点2的出度为2，入度为1

即节点2的出度为2，入度为1。