任选一个存储结构存储一个无向图,要求最少8个顶点,12个活动,完成如下功能: 1.创建图。接收从键盘输入的边信息,存储到图中。2.增加边的信息。 3.删除边的信息。 4.对图进行深度优先遍历。
时间: 2023-06-10 13:08:57 浏览: 112
C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列
5星 · 资源好评率100%
我建议使用邻接表作为存储结构,这种结构可以很好地支持插入和删除边操作,并且可以方便地进行深度优先遍历。
以下是一个简单的实现:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 邻接表中的边结构体
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
// 邻接表中的顶点结构体
struct Vertex {
int id;
vector<Edge> edges;
Vertex(int i) : id(i) {}
};
class Graph {
private:
vector<Vertex> vertices;
public:
// 创建图
void createGraph() {
int numVertices, numEdges;
cout << "请输入顶点数和边数:" << endl;
cin >> numVertices >> numEdges;
// 创建顶点
for (int i = 0; i < numVertices; i++) {
Vertex v(i);
vertices.push_back(v);
}
// 添加边
cout << "请输入边的信息(起点 终点 权重):" << endl;
for (int i = 0; i < numEdges; i++) {
int from, to, weight;
cin >> from >> to >> weight;
Edge e(to, weight);
vertices[from].edges.push_back(e);
// 因为是无向图,所以要添加反向边
Edge e2(from, weight);
vertices[to].edges.push_back(e2);
}
}
// 增加边的信息
void addEdge(int from, int to, int weight) {
Edge e(to, weight);
vertices[from].edges.push_back(e);
// 因为是无向图,所以要添加反向边
Edge e2(from, weight);
vertices[to].edges.push_back(e2);
}
// 删除边的信息
void removeEdge(int from, int to) {
// 删除 from 中的 to 边
for (auto it = vertices[from].edges.begin(); it != vertices[from].edges.end(); it++) {
if (it->to == to) {
vertices[from].edges.erase(it);
break;
}
}
// 删除 to 中的 from 边
for (auto it = vertices[to].edges.begin(); it != vertices[to].edges.end(); it++) {
if (it->to == from) {
vertices[to].edges.erase(it);
break;
}
}
}
// 深度优先遍历
void dfs(int start) {
vector<bool> visited(vertices.size(), false);
stack<int> stk;
stk.push(start);
visited[start] = true;
while (!stk.empty()) {
int cur = stk.top();
stk.pop();
cout << cur << " ";
for (auto e : vertices[cur].edges) {
int next = e.to;
if (!visited[next]) {
visited[next] = true;
stk.push(next);
}
}
}
}
};
int main() {
Graph g;
g.createGraph();
cout << "深度优先遍历:";
g.dfs(0);
cout << endl;
return 0;
}
```
这里的实现比较简单,仅供参考。在实际应用中,可能需要更复杂的数据结构来支持各种操作,例如使用邻接矩阵来支持快速查找和修改边。
阅读全文