用C语言写出代码和输入实例及结果:已知有向图采用邻接矩阵作为存储结构,设计算法求该图中每个顶点的出度和入度,
时间: 2024-03-26 07:35:48 浏览: 68
代码如下:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100
typedef struct {
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vex_num, arc_num; // 顶点数、弧数
} Graph;
// 初始化有向图
void init_graph(Graph *g, int vex_num, int arc_num) {
g->vex_num = vex_num;
g->arc_num = arc_num;
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
for (int j = 0; j < MAX_VERTEX_NUM; ++j) {
g->arcs[i][j] = 0; // 初始化邻接矩阵
}
}
}
// 添加弧
void add_arc(Graph *g, int start, int end) {
g->arcs[start][end] = 1;
}
// 求每个顶点的出度和入度
void get_degree(Graph g, int out_degree[], int in_degree[]) {
for (int i = 0; i < g.vex_num; ++i) {
out_degree[i] = 0;
in_degree[i] = 0;
for (int j = 0; j < g.vex_num; ++j) {
if (g.arcs[i][j]) { // 如果有弧 i -> j
out_degree[i]++; // i 的出度加 1
in_degree[j]++; // j 的入度加 1
}
}
}
}
int main() {
Graph g;
int out_degree[MAX_VERTEX_NUM], in_degree[MAX_VERTEX_NUM];
int vex_num, arc_num;
printf("请输入顶点数和弧数:");
scanf("%d%d", &vex_num, &arc_num);
init_graph(&g, vex_num, arc_num);
printf("请输入每条弧的起点和终点:\n");
for (int i = 0; i < arc_num; ++i) {
int start, end;
scanf("%d%d", &start, &end);
add_arc(&g, start, end);
}
get_degree(g, out_degree, in_degree);
printf("每个顶点的出度和入度分别为:\n");
for (int i = 0; i < vex_num; ++i) {
printf("顶点 %d:出度 %d,入度 %d\n", i, out_degree[i], in_degree[i]);
}
return 0;
}
```
输入实例:
```
请输入顶点数和弧数:4 5
请输入每条弧的起点和终点:
0 1
1 2
2 0
1 3
3 2
```
输出结果:
```
每个顶点的出度和入度分别为:
顶点 0:出度 1,入度 1
顶点 1:出度 2,入度 1
顶点 2:出度 1,入度 2
顶点 3:出度 1,入度 1
```
阅读全文