用C语言写出:已知有向图采用邻接矩阵作为存储结构,设计算法求该图中每个顶点的出度和入度
时间: 2024-03-26 21:35:33 浏览: 165
C++求有向图中某顶点的出度 数据结构.docx
以下是用C语言实现求有向图邻接矩阵中每个顶点的出度和入度的算法:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 定义邻接矩阵类型
typedef struct {
int vexs[MAX_VERTEX_NUM]; // 存储顶点信息
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的信息
int vex_num, arc_num; // 顶点数、边数
} MGraph;
// 初始化邻接矩阵
void InitMGraph(MGraph *G) {
int i, j;
printf("请输入顶点数和边数:");
scanf("%d%d", &(G->vex_num), &(G->arc_num));
printf("请输入顶点信息:");
for (i = 0; i < G->vex_num; ++i) {
scanf("%d", &(G->vexs[i]));
}
for (i = 0; i < G->vex_num; ++i) {
for (j = 0; j < G->vex_num; ++j) {
G->arcs[i][j] = 0; // 初始化为0,即无连接边
}
}
printf("请输入边的信息:\n");
for (i = 0; i < G->arc_num; ++i) {
int v1, v2;
printf("请输入第%d条边的两个顶点序号:", i+1);
scanf("%d%d", &v1, &v2);
G->arcs[v1][v2] = 1; // 有连接边的位置置为1
}
}
// 计算每个顶点的出度和入度
void CalInOutDegree(MGraph G, int *in_degree, int *out_degree) {
int i, j;
for (i = 0; i < G.vex_num; ++i) {
int in = 0, out = 0;
for (j = 0; j < G.vex_num; ++j) {
if (G.arcs[i][j] == 1) { // 有连接边,则出度+1
out++;
}
if (G.arcs[j][i] == 1) { // 有连接边,则入度+1
in++;
}
}
in_degree[i] = in;
out_degree[i] = out;
}
}
// 输出每个顶点的出度和入度
void PrintInOutDegree(MGraph G, int *in_degree, int *out_degree) {
int i;
printf("每个顶点的出度和入度如下:\n");
for (i = 0; i < G.vex_num; ++i) {
printf("顶点%d:出度%d,入度%d\n", G.vexs[i], out_degree[i], in_degree[i]);
}
}
int main() {
MGraph G;
int in_degree[MAX_VERTEX_NUM], out_degree[MAX_VERTEX_NUM];
InitMGraph(&G);
CalInOutDegree(G, in_degree, out_degree);
PrintInOutDegree(G, in_degree, out_degree);
return 0;
}
```
注意:该算法实现的是有向图邻接矩阵的存储结构,且默认顶点信息为整数,因此输入信息时顶点信息也需为整数。
阅读全文