设计一个程序,在无向图中删除一个顶点及相关边;邻接矩阵作为存储结构。算法思想: (1) 定义图的顺序存储结构; (2) 创建无向图,采用邻接矩阵表示(调用CreateUDG函数实现),具体实现如下: 输入图的顶点数和边数; 依次输入顶点的信息存入顶点表中; 初始化邻接矩阵,使每个权值初始化为0; 构造邻接矩阵;(需调用LocateVex函数获取顶点在顶点表中的下标) (3) 删除一个顶点v及相关边(调用DeleteVex函数实现)。 (4) 输出删除顶点v及其相关边后图的邻接矩阵(调用PrintUDG函数实现)。
时间: 2023-06-26 11:03:43 浏览: 129
以下是基于邻接矩阵存储结构的无向图删除顶点及相关边的程序实现:
```c++
#include <iostream>
using namespace std;
#define MAX_VERTEX_NUM 20
// 顶点表结构体
typedef struct {
int no; // 顶点编号
char info; // 顶点信息
}VertexType;
// 图的邻接矩阵存储结构体
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点表
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum; // 顶点数
int arcnum; // 边数
}MGraph;
// 获取顶点在顶点表中的下标
int LocateVex(MGraph &G, int v) {
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i].no == v) {
return i;
}
}
return -1;
}
// 创建无向图,采用邻接矩阵表示
void CreateUDG(MGraph &G) {
cout << "请输入顶点数和边数:" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "请输入每个顶点的信息:" << endl;
for (int i = 0; i < G.vexnum; i++) {
cout << "第" << i + 1 << "个顶点信息:";
cin >> G.vexs[i].info;
G.vexs[i].no = i + 1;
}
// 初始化邻接矩阵,使每个权值初始化为0
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0;
}
}
// 构造邻接矩阵
int v1, v2;
for (int k = 0; k < G.arcnum; k++) {
cout << "请输入一条边依附的顶点及其权值:" << endl;
cin >> v1 >> v2;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
if (i != -1 && j != -1) {
G.arcs[i][j] = 1;
G.arcs[j][i] = G.arcs[i][j]; // 无向图的邻接矩阵是对称的
}
}
}
// 删除一个顶点v及相关边
void DeleteVex(MGraph &G, int v) {
int i = LocateVex(G, v);
if (i == -1) {
cout << "不存在该顶点!" << endl;
return;
}
// 删除与该顶点相关的边
for (int j = 0; j < G.vexnum; j++) {
if (G.arcs[i][j] == 1) {
G.arcs[i][j] = 0;
G.arcs[j][i] = G.arcs[i][j];
}
}
// 删除该顶点
for (int k = i; k < G.vexnum - 1; k++) {
G.vexs[k] = G.vexs[k + 1];
for (int m = 0; m < G.vexnum; m++) {
G.arcs[m][k] = G.arcs[m][k + 1];
}
}
for (int k = i; k < G.vexnum - 1; k++) {
for (int n = 0; n < G.vexnum; n++) {
G.arcs[k][n] = G.arcs[k + 1][n];
}
}
G.vexnum--; // 顶点数减1
}
// 输出删除顶点v及其相关边后图的邻接矩阵
void PrintUDG(MGraph &G) {
cout << "删除顶点v及其相关边后图的邻接矩阵为:" << endl;
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
cout << G.arcs[i][j] << " ";
}
cout << endl;
}
}
int main() {
MGraph G;
CreateUDG(G);
int v;
cout << "请输入要删除的顶点:" << endl;
cin >> v;
DeleteVex(G, v);
PrintUDG(G);
return 0;
}
```
运行程序,输入顶点数、边数、顶点信息、边依附的顶点及其权值,再输入要删除的顶点,程序将输出删除顶点及其相关边后的图的邻接矩阵。
阅读全文