用C语言写一段程序:对于一个具有n个顶点、e条边的无向图,编程完成以下功能: 1)采用邻接矩阵表示法建立其存储结构并输出。 2)统计图中边的数目并输出。 3)统计各顶点的度并输出。
时间: 2023-06-26 09:05:53 浏览: 97
下面是用C语言实现的代码,实现了对于一个具有n个顶点、e条边的无向图,采用邻接矩阵表示法建立其存储结构并输出,统计图中边的数目并输出,统计各顶点的度并输出。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
// 存储结构体
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数目
int edge_num; // 边数目
} Graph;
// 初始化图
void initGraph(Graph* G) {
int i, j;
G->vertex_num = 0;
G->edge_num = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertex[i] = 0;
for (j = 0; j < MAX_VERTEX_NUM; j++) {
G->arc[i][j] = 0;
}
}
}
// 添加顶点
void addVertex(Graph* G, int v) {
if (G->vertex_num >= MAX_VERTEX_NUM) {
printf("Vertex number is out of range.\n");
return;
}
G->vertex[G->vertex_num++] = v;
}
// 添加边
void addEdge(Graph* G, int v1, int v2) {
int i, j;
for (i = 0; i < G->vertex_num; i++) {
if (G->vertex[i] == v1) {
for (j = 0; j < G->vertex_num; j++) {
if (G->vertex[j] == v2) {
G->arc[i][j] = 1;
G->arc[j][i] = 1;
G->edge_num++;
return;
}
}
}
}
}
// 输出邻接矩阵
void printGraph(Graph* G) {
int i, j;
printf("Adjacency matrix:\n");
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
printf("%d ", G->arc[i][j]);
}
printf("\n");
}
}
// 统计边数
void countEdges(Graph* G) {
printf("Number of edges: %d\n", G->edge_num);
}
// 统计各顶点的度
void countDegrees(Graph* G) {
int i, j, degree;
printf("Degrees of each vertex:\n");
for (i = 0; i < G->vertex_num; i++) {
degree = 0;
for (j = 0; j < G->vertex_num; j++) {
degree += G->arc[i][j];
}
printf("%d: %d\n", G->vertex[i], degree);
}
}
int main() {
Graph G;
int n, e, i, v1, v2;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &e);
initGraph(&G);
for (i = 0; i < n; i++) {
addVertex(&G, i + 1);
}
for (i = 0; i < e; i++) {
printf("Enter edge %d: ", i + 1);
scanf("%d%d", &v1, &v2);
addEdge(&G, v1, v2);
}
printGraph(&G);
countEdges(&G);
countDegrees(&G);
return 0;
}
```
使用方法:
1. 编译运行程序。
2. 输入顶点数目和边数目。
3. 依次输入每条边的两个顶点。
4. 输出邻接矩阵、边数和各顶点的度。
阅读全文