以邻接矩阵作为存储结构实现以下图的基本操作: 1.增加一个新顶点v,InsertVex(G, v); 2.删除顶点v及其相关的边,DeleteVex(G, v); 3.增加一条边<v,w>,InsertArc(G, v, w); 4.删除一条边<v,w>,DeleteArc(G, v, w)。,用c++代码实现,
时间: 2024-02-24 16:59:48 浏览: 65
好的,以下是使用邻接矩阵实现图的基本操作的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VERTICES = 100; // 最大顶点数
class Graph {
private:
vector<vector<int>> adjMatrix; // 邻接矩阵
int numVertices; // 顶点数
public:
// 构造函数
Graph() : numVertices(0) {
adjMatrix.resize(MAX_VERTICES);
for (auto& v : adjMatrix) {
v.resize(MAX_VERTICES);
}
}
// 插入一个新顶点
void InsertVex(int v) {
if (numVertices == MAX_VERTICES) {
cout << "Error: Exceeds maximum number of vertices." << endl;
return;
}
++numVertices;
for (int i = 0; i < numVertices; ++i) {
adjMatrix[i].resize(numVertices);
}
}
// 删除顶点及其相关的边
void DeleteVex(int v) {
if (v < 0 || v >= numVertices) {
cout << "Error: Invalid vertex index." << endl;
return;
}
--numVertices;
for (int i = v; i < numVertices; ++i) {
for (int j = 0; j < numVertices; ++j) {
adjMatrix[i][j] = adjMatrix[i+1][j];
}
}
for (int i = 0; i < numVertices; ++i) {
for (int j = v; j < numVertices; ++j) {
adjMatrix[i][j] = adjMatrix[i][j+1];
}
}
for (auto& v : adjMatrix) {
v.resize(numVertices);
}
}
// 插入一条边<v, w>
void InsertArc(int v, int w) {
if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) {
cout << "Error: Invalid vertex index." << endl;
return;
}
adjMatrix[v][w] = 1;
adjMatrix[w][v] = 1; // 无向图需要反向再连接一次
}
// 删除一条边<v, w>
void DeleteArc(int v, int w) {
if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) {
cout << "Error: Invalid vertex index." << endl;
return;
}
adjMatrix[v][w] = 0;
adjMatrix[w][v] = 0; // 无向图需要反向再删除一次
}
// 打印邻接矩阵
void PrintMatrix() {
cout << "Adjacency Matrix: " << endl;
for (int i = 0; i < numVertices; ++i) {
for (int j = 0; j < numVertices; ++j) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
Graph G;
G.InsertVex(0);
G.InsertVex(1);
G.InsertVex(2);
G.InsertArc(0, 1);
G.InsertArc(1, 2);
G.PrintMatrix();
G.DeleteArc(0, 1);
G.DeleteVex(1);
G.PrintMatrix();
return 0;
}
```
这个实现使用了一个二维向量 `adjMatrix` 来表示邻接矩阵,并提供了四个基本操作: `InsertVex()` 插入一个新顶点, `DeleteVex()` 删除顶点及其相关的边, `InsertArc()` 插入一条边, `DeleteArc()` 删除一条边。同时,还提供了一个 `PrintMatrix()` 函数用于打印邻接矩阵。
阅读全文