统计有向图邻接矩阵的各个结点的入度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 列表。

相关问题

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。

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

邻接矩阵是一种表示图的数据结构，对于有向图而言，邻接矩阵可以采用以下方式实现：

1. 创建一个大小为n*n的二维数组，其中n为有向图中的节点数；
2. 对于有向边(i,j)，邻接矩阵中第i行第j列的元素值为1，表示从节点i到节点j有一条有向边；
3. 如果有向边(i,j)不存在，则邻接矩阵中第i行第j列的元素值为0。

举个例子，对于如下有向图：

   1 ------> 2 <------ 3
   |         |         |
   |         |         |
   v         v         v
   4 ------->5-------->6

其邻接矩阵可以表示为：

  1  2  3  4  5  6
1 0  1  0  1  0  0
2 0  0  1  0  1  0
3 0  0  0  0  1  1
4 0  0  0  0  0  1
5 0  0  0  0  0  0
6 0  0  0  0  0  0

其中，第i行的元素之和即为第i个节点的出度，第i列的元素之和即为第i个节点的入度。

使用图的非递归搜索算法求出该有向图结点的度，可以采用BFS算法或DFS算法实现。下面以BFS算法为例：

def bfs(adj_matrix, node):
    queue = [node]
    visited = set()
    while queue:
        cur_node = queue.pop(0)
        if cur_node not in visited:
            visited.add(cur_node)
            for i in range(len(adj_matrix)):
                if adj_matrix[cur_node][i] == 1:
                    queue.append(i)
    return visited

# 计算节点的度
def get_degree(adj_matrix, node):
    # 计算出度
    out_degree = sum(adj_matrix[node])
    # 计算入度
    in_degree = len(bfs(adj_matrix.transpose(), node))
    return out_degree, in_degree

# 示例
adj_matrix = [[0, 1, 0, 1, 0, 0],
              [0, 0, 1, 0, 1, 0],
              [0, 0, 0, 0, 1, 1],
              [0, 0, 0, 0, 0, 1],
              [0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0]]
node = 2
out_degree, in_degree = get_degree(adj_matrix, node)
print("节点{}的出度为{}，入度为{}".format(node, out_degree, in_degree))

输出结果为：

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

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