C语言求解有向图的出度入度
时间: 2023-09-06 16:11:13 浏览: 52
求解有向图的出度和入度需要遍历整个图,对于每个顶点,统计其出边和入边的数量即可。
以下是用C语言实现求解有向图出度和入度的示例代码:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100 // 最多顶点数
int main() {
int v[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int inDegree[MAX_VERTEX_NUM] = {0}; // 入度数组
int outDegree[MAX_VERTEX_NUM] = {0}; // 出度数组
int vertexNum, edgeNum; // 顶点数和边数
// 读入顶点数和边数
printf("请输入顶点数和边数:");
scanf("%d%d", &vertexNum, &edgeNum);
// 初始化邻接矩阵
for(int i = 0; i < vertexNum; i++) {
for(int j = 0; j < vertexNum; j++) {
v[i][j] = 0;
}
}
// 读入边
printf("请输入每条边的起点和终点(顶点从0开始编号):\n");
for(int i = 0; i < edgeNum; i++) {
int start, end;
scanf("%d%d", &start, &end);
v[start][end] = 1; // 标记邻接矩阵中对应位置为1
}
// 统计入度和出度
for(int i = 0; i < vertexNum; i++) {
for(int j = 0; j < vertexNum; j++) {
if(v[i][j] == 1) { // 有一条从i到j的边
outDegree[i]++; // i的出度+1
inDegree[j]++; // j的入度+1
}
}
}
// 输出结果
printf("顶点 出度 入度\n");
for(int i = 0; i < vertexNum; i++) {
printf("%d %d %d\n", i, outDegree[i], inDegree[i]);
}
return 0;
}
```
该代码实现了从标准输入中读入有向图的顶点数和边数,再读入每条边的起点和终点,并使用邻接矩阵来表示有向图。然后统计每个顶点的入度和出度,并输出结果。