邻接表作为存储结构,实现以下图的基本操作: 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 22:00:06 浏览: 110
当邻接表的存储结构形成后图便唯一确定!-数据结构(清华大学版)——图
好的,以下是使用邻接表实现图的基本操作的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 邻接表存储图的结构体
struct Graph {
// 顶点的个数
int num_vertices;
// 邻接表
vector<vector<int>> adj_list;
};
// 初始化图
void initGraph(Graph* G, int num_vertices) {
G->num_vertices = num_vertices;
G->adj_list.resize(num_vertices);
}
// 增加一个新顶点v
void InsertVex(Graph* G, int v) {
G->num_vertices++;
G->adj_list.resize(G->num_vertices);
}
// 删除顶点v及其相关的边
void DeleteVex(Graph* G, int v) {
// 删除v与其他顶点的边
for (int i = 0; i < G->num_vertices; i++) {
if (i == v) continue;
for (vector<int>::iterator it = G->adj_list[i].begin(); it != G->adj_list[i].end(); ) {
if (*it == v) {
it = G->adj_list[i].erase(it);
} else {
it++;
}
}
}
// 删除v的邻接表
G->adj_list[v].clear();
// 删除v
G->num_vertices--;
}
// 增加一条边<v,w>
void InsertArc(Graph* G, int v, int w) {
G->adj_list[v].push_back(w);
}
// 删除一条边<v,w>
void DeleteArc(Graph* G, int v, int w) {
for (vector<int>::iterator it = G->adj_list[v].begin(); it != G->adj_list[v].end(); ) {
if (*it == w) {
it = G->adj_list[v].erase(it);
} else {
it++;
}
}
}
int main() {
Graph G;
initGraph(&G, 5);
InsertArc(&G, 0, 1);
InsertArc(&G, 0, 2);
InsertArc(&G, 1, 3);
InsertArc(&G, 2, 3);
InsertArc(&G, 3, 4);
cout << "原图:" << endl;
for (int i = 0; i < G.num_vertices; i++) {
cout << i << ": ";
for (int j = 0; j < G.adj_list[i].size(); j++) {
cout << G.adj_list[i][j] << " ";
}
cout << endl;
}
InsertVex(&G, 5);
DeleteVex(&G, 2);
DeleteArc(&G, 1, 3);
cout << "修改后的图:" << endl;
for (int i = 0; i < G.num_vertices; i++) {
cout << i << ": ";
for (int j = 0; j < G.adj_list[i].size(); j++) {
cout << G.adj_list[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
这段代码中,我们使用 `vector<vector<int>>` 来表示邻接表,其中外层的 `vector` 表示图的所有顶点,内层的 `vector` 则表示该顶点的所有邻居。具体实现中,我们通过 `resize()` 函数来初始化邻接表,通过 `push_back()` 函数来增加邻居,通过 `erase()` 函数来删除邻居。在删除顶点时,我们需要同时删除该顶点与其他顶点的所有边,因此需要对所有邻接表进行遍历。
阅读全文