编写一个能够创建4种不同类型图的邻接矩阵存储的通用函数,函数格式如下: CreateMGraph(GraphKind GKind, MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs)
时间: 2024-03-05 22:52:50 浏览: 40
好的,我可以为你编写这个函数。以下是函数的代码:
```c++
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 图的类型
typedef enum {
DG, // 有向图
DN, // 有向网
UG, // 无向图
UDN // 无向网
}GraphKind;
// 边的结构体
typedef struct {
int weight; // 权值
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
// 图的结构体
typedef struct {
char vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 顶点数和边数
GraphKind kind; // 图的类型
}MGraph;
// 创建有向图的邻接矩阵存储
void createDG(MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.kind = DG;
G.vexnum = vexnum;
G.arcnum = arcnum;
for (int i = 0; i < vexnum; i++) {
G.vexs[i] = vexs[i];
}
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
G.arcs[i][j].weight = 0;
}
}
for (int k = 0; k < arcnum; k++) {
int i = arcs[k * 2];
int j = arcs[k * 2 + 1];
G.arcs[i][j].weight = 1;
}
}
// 创建有向网的邻接矩阵存储
void createDN(MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.kind = DN;
G.vexnum = vexnum;
G.arcnum = arcnum;
for (int i = 0; i < vexnum; i++) {
G.vexs[i] = vexs[i];
}
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
G.arcs[i][j].weight = INT_MAX;
}
}
for (int k = 0; k < arcnum; k++) {
int i = arcs[k * 3];
int j = arcs[k * 3 + 1];
int w = arcs[k * 3 + 2];
G.arcs[i][j].weight = w;
}
}
// 创建无向图的邻接矩阵存储
void createUG(MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.kind = UG;
G.vexnum = vexnum;
G.arcnum = arcnum;
for (int i = 0; i < vexnum; i++) {
G.vexs[i] = vexs[i];
}
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
G.arcs[i][j].weight = 0;
}
}
for (int k = 0; k < arcnum; k++) {
int i = arcs[k * 2];
int j = arcs[k * 2 + 1];
G.arcs[i][j].weight = 1;
G.arcs[j][i].weight = 1;
}
}
// 创建无向网的邻接矩阵存储
void createUDN(MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.kind = UDN;
G.vexnum = vexnum;
G.arcnum = arcnum;
for (int i = 0; i < vexnum; i++) {
G.vexs[i] = vexs[i];
}
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
G.arcs[i][j].weight = INT_MAX;
}
}
for (int k = 0; k < arcnum; k++) {
int i = arcs[k * 3];
int j = arcs[k * 3 + 1];
int w = arcs[k * 3 + 2];
G.arcs[i][j].weight = w;
G.arcs[j][i].weight = w;
}
}
// 创建图的邻接矩阵存储
void CreateMGraph(GraphKind GKind, MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
switch (GKind) {
case DG:
createDG(G, vexnum, arcnum, vexs, arcs);
break;
case DN:
createDN(G, vexnum, arcnum, vexs, arcs);
break;
case UG:
createUG(G, vexnum, arcnum, vexs, arcs);
break;
case UDN:
createUDN(G, vexnum, arcnum, vexs, arcs);
break;
default:
break;
}
}
```
这个函数接受4个参数:图的类型,图的结构体G,顶点数,边数,顶点数组vexs和边数组arcs。在函数的内部,我们根据不同的图的类型,调用不同的函数来创建邻接矩阵存储的图。每个函数都遍历顶点和边数组,将它们添加到邻接矩阵中,最终将图的结构体G返回。
阅读全文