用C语言代码算求有向图中每个顶点的入度和出度
时间: 2024-03-13 08:48:16 浏览: 19
假设有向图用邻接矩阵表示,其中n个顶点的编号为0到n-1,则可以通过以下C语言代码计算每个顶点的入度和出度:
```c
#include <stdio.h>
#define MAX_N 100
// 假设图用邻接矩阵表示,matrix[i][j] 表示从顶点 i 到顶点 j 是否有一条有向边
// n 表示顶点数
void calc_degrees(int matrix[MAX_N][MAX_N], int n) {
int indegrees[MAX_N] = {0};
int outdegrees[MAX_N] = {0};
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (matrix[i][j]) {
outdegrees[i]++;
indegrees[j]++;
}
}
}
printf("Vertex\tIndegree\tOutdegree\n");
for (i = 0; i < n; i++) {
printf("%d\t%d\t%d\n", i, indegrees[i], outdegrees[i]);
}
}
int main() {
// 示例图中的邻接矩阵表示
int matrix[MAX_N][MAX_N] = {
{0, 1, 0, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
int n = 4;
calc_degrees(matrix, n);
return 0;
}
```
上述代码中,我们用两个数组分别记录每个顶点的入度和出度。在计算时,我们遍历整个邻接矩阵,如果从顶点i到顶点j有一条边,则顶点i的出度加1,顶点j的入度加1。最后输出每个顶点的编号、入度和出度。