离散数学已知有向图求邻接矩阵c语言
时间: 2023-06-27 12:05:01 浏览: 87
假设有 $n$ 个节点的有向图,我们可以使用一个 $n\times n$ 的矩阵来表示其邻接关系,其中第 $i$ 行第 $j$ 列的元素为 $1$ 表示存在一条从节点 $i$ 到节点 $j$ 的有向边,否则为 $0$。
下面是一个简单的 C 语言程序,用于从输入中读取有向图的边,然后生成其邻接矩阵:
```c
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, m; // n: 节点数,m: 边数
scanf("%d %d", &n, &m);
int **adj_matrix = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
adj_matrix[i] = (int *)calloc(n, sizeof(int));
}
for (int i = 0; i < m; i++) {
int u, v; // 边的起点和终点
scanf("%d %d", &u, &v);
adj_matrix[u][v] = 1;
}
// 输出邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", adj_matrix[i][j]);
}
printf("\n");
}
// 释放内存
for (int i = 0; i < n; i++) {
free(adj_matrix[i]);
}
free(adj_matrix);
return 0;
}
```
该程序首先读取节点数 $n$ 和边数 $m$,然后使用动态内存分配创建一个 $n\times n$ 的二维数组 `adj_matrix`,并将所有元素初始化为 $0$。接下来,程序从输入中读取每条边的起点和终点,并在邻接矩阵中标记相应的位置。最后,程序输出邻接矩阵,并释放动态内存。