当前位置：首页 > ops >正文

【PTA数据结构 | C语言版】邻接矩阵表示的图基本操作

ops 2025/7/22 7:18:18

本专栏持续输出数据结构题目集，欢迎订阅。

文章目录

- 题目
- 代码

题目

请编写程序，实现并测试邻接矩阵表示的图的以下基本操作：

获取图的顶点个数
判断边是否存在
找顶点的第一个邻接点
向图中插入边
从图中删除边
从图中删除顶点及所有邻接于该顶点的边

注意：此处默认邻接矩阵点的删除方法是用最后一个点把要删除的点覆盖掉。

输入格式：
输入首先在第一行给出两个正整数，依次为：kMaxVertex（≤10，图中最大顶点数量）和 no_edge_value（≤2^30，邻接矩阵中表示“没有边”的值）。
第二行给出两个正整数，依次为当前要创建的图的顶点数 n 和边数 m（保证顶点数至少为 1 且不超过最大顶点数量）。
第三行给出 n 个英文字母，顺序对应每个顶点的信息。
随后 m 行，每行给出一条有向边的起点编号、终点编号、权重。顶点编号从 0 开始，权重（≤2^30）为整数。
结束了图的信息之后，接下来 2 行，每行给出一条待检查的有向边的起点编号、终点编号，用于检查边的存在性。
接下来给出一个顶点编号，用于检查该顶点的第一个邻接点。
随后给出一条待删除的有向边的起点编号、终点编号。
最后给出待删除顶点的编号。
同行数字、字符均以一个空格分隔。

输出格式：
参考样例。
首先第一行输出邻接矩阵为：。随后 n 行，顺序输出邻接矩阵每一行的值。简单起见，同行每个数字后面跟 1 个空格。
完成了邻接矩阵输出后，下一行输出顶点数 = x，其中 x 是图中顶点数。
对于待检查的两条有向边，按格式 <u, v> 的存在性 = x 输出其存在性检查结果，其中 u 为边的起点编号，v 为边的终点编号，x 为 0 表示不存在，为 1 表示存在。
对于下一个给出的顶点，按格式顶点x的第一个邻接点 = y 输出第一个邻接点的检查结果，其中 x 为给定顶点编号，y 为其第一个邻接点（即编号最小的邻接点）的编号。
对于下一条待删除的边，首先从图中删除之，随后输出该边的存在性检查结果，格式与前次存在性检查相同。
对于最后要删除的顶点，首先按格式待删除的顶点信息为 x 输出该顶点的信息字符 x，随后将其从图中删除。
最后输出结果矩阵的信息，格式为：
在一行中输出当前顶点数 = x，其中 x 为图中顶点数；
在一行中输出当前边数 = y，其中 y 为图中边数；
在一行中顺序输出每个顶点的信息，中间没有空格；
在一行中输出邻接矩阵为：；
按照输出初始矩阵的相同格式输出结果图的邻接矩阵。

输入样例：
10 0
5 7
a b c d e
0 2 1
2 0 2
2 3 1
3 0 3
3 4 4
2 4 2
4 0 5
1 3
3 4
2
3 0
2

输出样例：

邻接矩阵为：
0 0 1 0 0 
0 0 0 0 0 
2 0 0 1 2 
3 0 0 0 4 
5 0 0 0 0 
顶点数 = 5
<1, 3> 的存在性 = 0
<3, 4> 的存在性 = 1
顶点2的第一个邻接点 = 0
<3, 0> 的存在性 = 0
待删除的顶点信息为 c
当前顶点数 = 4
当前边数 = 2
abed
邻接矩阵为：
0 0 0 0 
0 0 0 0 
5 0 0 0 
0 0 4 0

代码

#include <stdio.h>
#include <stdlib.h>#define MAX_VERTEX 10typedef struct {int vertices[MAX_VERTEX][MAX_VERTEX];  // 邻接矩阵char data[MAX_VERTEX];                 // 顶点信息int n;                                 // 当前顶点数int m;                                 // 当前边数int maxVertex;                         // 最大顶点数int noEdgeValue;                       // 表示无边的值
} Graph;// 初始化图
void initGraph(Graph *g, int maxVertex, int noEdgeValue) {g->maxVertex = maxVertex;g->noEdgeValue = noEdgeValue;g->n = 0;g->m = 0;for (int i = 0; i < maxVertex; i++) {for (int j = 0; j < maxVertex; j++) {g->vertices[i][j] = noEdgeValue;}}
}// 插入边
void insertEdge(Graph *g, int u, int v, int weight) {if (g->vertices[u][v] == g->noEdgeValue) {g->m++;}g->vertices[u][v] = weight;
}// 删除边
void deleteEdge(Graph *g, int u, int v) {if (g->vertices[u][v] != g->noEdgeValue) {g->m--;}g->vertices[u][v] = g->noEdgeValue;
}// 删除顶点
void deleteVertex(Graph *g, int v) {// 减少边数：删除所有从v出发的边for (int i = 0; i < g->n; i++) {if (g->vertices[v][i] != g->noEdgeValue) {g->m--;}}// 减少边数：删除所有进入v的边for (int i = 0; i < g->n; i++) {if (g->vertices[i][v] != g->noEdgeValue) {g->m--;}}// 用最后一个顶点覆盖要删除的顶点if (v < g->n - 1) {// 复制最后一个顶点的信息g->data[v] = g->data[g->n - 1];// 复制最后一个顶点的入边for (int i = 0; i < g->n; i++) {g->vertices[i][v] = g->vertices[i][g->n - 1];}// 复制最后一个顶点的出边for (int i = 0; i < g->n; i++) {g->vertices[v][i] = g->vertices[g->n - 1][i];}}// 减少顶点数g->n--;// 清除最后一行和最后一列（现在是多余的）for (int i = 0; i < g->n; i++) {g->vertices[i][g->n] = g->noEdgeValue;g->vertices[g->n][i] = g->noEdgeValue;}
}// 检查边是否存在
int edgeExists(Graph *g, int u, int v) {return (g->vertices[u][v] != g->noEdgeValue);
}// 查找第一个邻接点
int firstAdjacent(Graph *g, int u) {for (int v = 0; v < g->n; v++) {if (g->vertices[u][v] != g->noEdgeValue) {return v;}}return -1;  // 没有邻接点
}// 输出邻接矩阵
void printMatrix(Graph *g) {printf("邻接矩阵为：\n");for (int i = 0; i < g->n; i++) {for (int j = 0; j < g->n; j++) {printf("%d ", g->vertices[i][j]);}printf("\n");}
}int main() {int maxVertex, noEdgeValue;scanf("%d %d", &maxVertex, &noEdgeValue);Graph g;initGraph(&g, maxVertex, noEdgeValue);int n, m;scanf("%d %d", &n, &m);g.n = n;// 读取顶点信息for (int i = 0; i < n; i++) {scanf(" %c", &g.data[i]);}// 读取边信息for (int i = 0; i < m; i++) {int u, v, weight;scanf("%d %d %d", &u, &v, &weight);insertEdge(&g, u, v, weight);}// 输出初始邻接矩阵printMatrix(&g);printf("顶点数 = %d\n", g.n);// 检查两条边的存在性int u, v;scanf("%d %d", &u, &v);printf("<%d, %d> 的存在性 = %d\n", u, v, edgeExists(&g, u, v));scanf("%d %d", &u, &v);printf("<%d, %d> 的存在性 = %d\n", u, v, edgeExists(&g, u, v));// 查找第一个邻接点int vertex;scanf("%d", &vertex);int adj = firstAdjacent(&g, vertex);printf("顶点%d的第一个邻接点 = %d\n", vertex, adj);// 删除一条边scanf("%d %d", &u, &v);deleteEdge(&g, u, v);printf("<%d, %d> 的存在性 = %d\n", u, v, edgeExists(&g, u, v));// 删除一个顶点scanf("%d", &vertex);printf("待删除的顶点信息为 %c\n", g.data[vertex]);deleteVertex(&g, vertex);// 输出结果信息printf("当前顶点数 = %d\n", g.n);printf("当前边数 = %d\n", g.m);// 输出顶点信息for (int i = 0; i < g.n; i++) {printf("%c", g.data[i]);}printf("\n");// 输出结果邻接矩阵printMatrix(&g);return 0;
}