设计巭个实现创建无向网的程序;邻巁矩阵作巟存储结构。算法思想: (1) 定义图的顺序存储结构; (2) 创建无向网,采用邻巁矩阵表示(调用CreateUDN函数实现),具体实现如下: 输入图的顶点数和边数; 依次输入顶点的巬息存入顶点表中; 匘始化邻巁矩阵,使巪个权值匘始化巟极大值; 构造邻巁矩阵;(需调用LocateVex函数获取顶点在顶点表中的下标) (3) 输巰图的邻巁矩阵(调用PrintUDN函数实现)。 注意:顶点数据仅巟1个数字或1个字符。 输入说明: 第巭行输入图的顶点数和边数; 第二行依次输入巪个顶点的数据; 其余各行的巪行输入巭条边的巬息。 输巰说明: 输巰图的邻巁矩阵,其中巪个值用6个宽度输巰且右对齐,最大值输巰∞。 输入样例: 4 5 A B C D A B 500 A C 200 A D 150 B C 400 C D 600 输巰样例: ∞ 500 200 150 500 ∞ 400 ∞ 200 400 ∞ 600 150 ∞ 600 ∞C语言实现
时间: 2023-06-10 08:06:21 浏览: 87
建立有向网络的邻接矩阵算法
以下是基于C语言实现的创建无向网的程序,使用邻接矩阵作为存储结构:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20
#define INFINITY 65535
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点表
EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, edgenum; // 顶点数和边数
} MGraph;
// 返回顶点v在图中的位置
int LocateVex(MGraph G, VertexType v) {
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == v) {
return i;
}
}
return -1;
}
// 创建无向网
void CreateUDN(MGraph *G) {
printf("请输入顶点数和边数:");
scanf("%d %d", &(G->vexnum), &(G->edgenum));
getchar(); // 吸收换行符
printf("请输入%d个顶点的信息:", G->vexnum);
for (int i = 0; i < G->vexnum; i++) {
scanf("%c", &(G->vexs[i]));
getchar(); // 吸收换行符
}
// 初始化邻接矩阵
for (int i = 0; i < G->vexnum; i++) {
for (int j = 0; j < G->vexnum; j++) {
G->edges[i][j] = INFINITY; // 将所有边的权重初始化为极大值
}
}
// 构造邻接矩阵
for (int k = 0; k < G->edgenum; k++) {
printf("请输入第%d条边的两个顶点和权值:", k+1);
VertexType v1, v2;
EdgeType weight;
scanf("%c %c %d", &v1, &v2, &weight);
getchar(); // 吸收换行符
int i = LocateVex(*G, v1);
int j = LocateVex(*G, v2);
G->edges[i][j] = G->edges[j][i] = weight;
}
}
// 打印无向网的邻接矩阵
void PrintUDN(MGraph G) {
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
if (G.edges[i][j] == INFINITY) {
printf("%6s", "∞");
} else {
printf("%6d", G.edges[i][j]);
}
}
printf("\n");
}
}
int main() {
MGraph G;
CreateUDN(&G);
PrintUDN(G);
return 0;
}
```
以上程序通过输入顶点数和边数来创建无向网,然后依次输入各个顶点的信息,最后输入每条边的两个顶点和权值来构造邻接矩阵。打印邻接矩阵时,将边的权值为无穷大的地方输出"∞",其他地方输出对应的权值。
阅读全文