帮我写代码,要求/*任选一个存储结构存储一个无向图,要求最少八个顶点,12个活动,完成如下功能 1.创建图。接受从键盘输入的边信息,存储到图中 2.增加边的信息 3.删除边的信息 4.对图进行深度优先遍历 */
时间: 2024-05-08 18:22:21 浏览: 97
好的,以下是代码实现:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 定义无向图类
class Graph {
private:
int vertex; // 图中顶点数
vector<vector<int>> adjList; // 邻接表存储结构
public:
// 构造函数
Graph(int v) {
vertex = v;
adjList.resize(vertex);
}
// 添加边
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // 无向图需要添加反向边
}
// 删除边
void removeEdge(int u, int v) {
for (auto it = adjList[u].begin(); it != adjList[u].end(); it++) {
if (*it == v) {
adjList[u].erase(it);
break;
}
}
for (auto it = adjList[v].begin(); it != adjList[v].end(); it++) {
if (*it == u) {
adjList[v].erase(it);
break;
}
}
}
// 深度优先遍历
void DFS(int v) {
vector<bool> visited(vertex, false); // 记录每个顶点是否被访问过
stack<int> s; // 用栈来实现深度优先遍历
s.push(v); // 将起始顶点压入栈中
visited[v] = true; // 标记起始顶点已被访问
while (!s.empty()) {
int curr = s.top(); // 取出栈顶元素
s.pop();
cout << curr << " "; // 访问当前顶点
// 遍历当前顶点的所有邻居顶点
for (auto neighbor : adjList[curr]) {
if (!visited[neighbor]) { // 如果邻居顶点未被访问,将其压入栈中
visited[neighbor] = true;
s.push(neighbor);
}
}
}
}
};
int main() {
// 创建一个包含8个顶点的无向图
Graph g(8);
// 接受从键盘输入的边信息,存储到图中
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
g.addEdge(3, 7);
g.addEdge(4, 7);
g.addEdge(5, 7);
g.addEdge(6, 7);
g.addEdge(0, 7);
g.addEdge(2, 3);
// 对图进行深度优先遍历
cout << "深度优先遍历结果:";
g.DFS(0);
// 增加边的信息
g.addEdge(1, 6);
cout << "\n增加一条边后的深度优先遍历结果:";
g.DFS(0);
// 删除边的信息
g.removeEdge(0, 7);
cout << "\n删除一条边后的深度优先遍历结果:";
g.DFS(0);
return 0;
}
```
以上代码中,我们采用邻接表的存储结构来表示无向图。在创建图时,我们使用 `addEdge` 函数来添加边信息。在深度优先遍历时,我们使用栈来实现,先将起始顶点压入栈中,然后遍历当前顶点的所有邻居顶点,将未被访问的邻居顶点压入栈中,直到栈为空。增加和删除边的操作都很简单,只需要在邻接表中查找并删除对应的边即可。
阅读全文