本题要求建立一个无向图,采用邻接矩阵做为存储结构。 例如 image.png 函数接口定义: void CreatMGraph(MGraph &G);//创建图G int locate(MGraph G,char v);//返回顶点v的下标 G 为图,采用邻接矩阵存储结构,v 是顶点的值。
时间: 2024-03-26 22:35:16 浏览: 32
根据函数接口定义和题目要求,可以参考以下代码实现创建无向图并用邻接矩阵存储:
```c++
#include <iostream>
using namespace std;
#define MAX_VERTEX_NUM 100 // 最大节点数
// 邻接矩阵存储的图结构体
typedef struct {
char vexs[MAX_VERTEX_NUM]; // 顶点集合
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵,记录边信息
int vexnum, arcnum; // 图的顶点数和边数
} MGraph;
// 返回顶点 v 的下标,如果不存在返回 -1
int locate(MGraph G, char v)
{
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == v) {
return i;
}
}
return -1;
}
// 创建无向图
void CreatMGraph(MGraph& G)
{
cout << "请输入节点数和边数:" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "请输入节点信息:" << endl;
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vexs[i];
}
// 初始化邻接矩阵
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0; // 初始值为 0,表示没有边相连
}
}
cout << "请输入边信息:" << endl;
for (int k = 0; k < G.arcnum; k++) {
char v1, v2;
cout << "请输入第" << k + 1 << "条边的两个端点:" << endl;
cin >> v1 >> v2;
int i = locate(G, v1);
int j = locate(G, v2);
if (i == -1 || j == -1) {
cout << "输入的节点信息有误!" << endl;
return;
}
G.arcs[i][j] = 1; // 标记节点 i 和节点 j 相连
G.arcs[j][i] = 1; // 由于是无向图,节点 j 和节点 i 也相连
}
}
int main()
{
MGraph G;
CreatMGraph(G);
// 输出邻接矩阵
cout << "邻接矩阵为:" << endl;
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
cout << G.arcs[i][j] << ' ';
}
cout << endl;
}
return 0;
}
```
注意,在输入边信息时,需要先通过 `locate` 函数找到两个节点在邻接矩阵中的下标,然后将它们标记为相连。由于是无向图,需要同时标记节点 j 和节点 i 相连。