编写一个能够创建4种不同类型图的邻接矩阵存储的通用函数,函数格式如下: CreateMGraph(GraphKind GKind, MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs)
时间: 2024-03-05 10:52:39 浏览: 21
以下是一个创建4种不同类型图的邻接矩阵存储的通用函数的示例代码,其中包括无向图、有向图、无向带权图和有向带权图。
```
#include <iostream>
#include <cstring>
using namespace std;
#define MAXVEX 100 // 最大顶点数
// 边的结构体
typedef struct {
int adj; // 顶点间是否有边
int weight; // 权值
} ArcCell, AdjMatrix[MAXVEX][MAXVEX];
// 图的结构体
typedef struct {
char vexs[MAXVEX]; // 顶点集合
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 顶点数和边数
int kind; // 图的类型
} MGraph;
// 图的种类
enum GraphKind {
UDG, // 无向图
DG, // 有向图
UDN, // 无向网
DN // 有向网
};
// 创建无向图的邻接矩阵存储
void CreateUDG(MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
int i, j, k;
G.vexnum = vexnum;
G.arcnum = arcnum;
memcpy(G.vexs, vexs, G.vexnum * sizeof(char));
memset(G.arcs, 0, sizeof(G.arcs));
for (k = 0; k < G.arcnum; k++) {
i = arcs[k * 2] - 'A';
j = arcs[k * 2 + 1] - 'A';
G.arcs[i][j].adj = 1;
G.arcs[j][i].adj = 1;
}
}
// 创建有向图的邻接矩阵存储
void CreateDG(MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
int i, j, k;
G.vexnum = vexnum;
G.arcnum = arcnum;
memcpy(G.vexs, vexs, G.vexnum * sizeof(char));
memset(G.arcs, 0, sizeof(G.arcs));
for (k = 0; k < G.arcnum; k++) {
i = arcs[k * 2] - 'A';
j = arcs[k * 2 + 1] - 'A';
G.arcs[i][j].adj = 1;
}
}
// 创建无向带权图的邻接矩阵存储
void CreateUDN(MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
int i, j, k, w;
G.vexnum = vexnum;
G.arcnum = arcnum;
memcpy(G.vexs, vexs, G.vexnum * sizeof(char));
memset(G.arcs, 0, sizeof(G.arcs));
for (k = 0; k < G.arcnum; k++) {
i = arcs[k * 3] - 'A';
j = arcs[k * 3 + 1] - 'A';
w = arcs[k * 3 + 2];
G.arcs[i][j].adj = 1;
G.arcs[j][i].adj = 1;
G.arcs[i][j].weight = w;
G.arcs[j][i].weight = w;
}
}
// 创建有向带权图的邻接矩阵存储
void CreateDN(MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
int i, j, k, w;
G.vexnum = vexnum;
G.arcnum = arcnum;
memcpy(G.vexs, vexs, G.vexnum * sizeof(char));
memset(G.arcs, 0, sizeof(G.arcs));
for (k = 0; k < G.arcnum; k++) {
i = arcs[k * 3] - 'A';
j = arcs[k * 3 + 1] - 'A';
w = arcs[k * 3 + 2];
G.arcs[i][j].adj = 1;
G.arcs[i][j].weight = w;
}
}
// 创建图的邻接矩阵存储
void CreateMGraph(GraphKind GKind, MGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.kind = GKind;
switch (G.kind) {
case UDG:
CreateUDG(G, vexnum, arcnum, vexs, arcs);
break;
case DG:
CreateDG(G, vexnum, arcnum, vexs, arcs);
break;
case UDN:
CreateUDN(G, vexnum, arcnum, vexs, arcs);
break;
case DN:
CreateDN(G, vexnum, arcnum, vexs, arcs);
break;
default:
break;
}
}
int main() {
MGraph G;
int vexnum = 5;
int arcnum = 5;
char vexs[MAXVEX] = {'A', 'B', 'C', 'D', 'E'};
int arcs[20] = {0, 1, 0, 2, 1, 2, 1, 3, 2, 4};
CreateMGraph(UDG, G, vexnum, arcnum, vexs, arcs);
return 0;
}
```
需要注意的是,这只是一个示例代码,实际使用时需要根据具体需求进行修改和优化。