C++实现图的基本操作代码
时间: 2024-03-26 18:40:31 浏览: 19
以下是使用邻接表实现图的基本操作的C++代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
struct GraphNode {
int val; // 顶点编号
vector<int> neighbors; // 与该顶点相连的所有顶点
GraphNode(int x) : val(x) {}
};
class Graph {
public:
// 添加顶点
void addNode(int val) {
GraphNode node(val);
nodes.push_back(node);
}
// 添加边
void addEdge(int src, int dst) {
nodes[src].neighbors.push_back(dst);
nodes[dst].neighbors.push_back(src); // 无向图需要加上这行
}
// 删除顶点
void deleteNode(int val) {
for (auto& node : nodes) {
for (int i = 0; i < node.neighbors.size(); ++i) {
if (node.neighbors[i] == val) {
node.neighbors.erase(node.neighbors.begin() + i);
break;
}
}
}
for (int i = 0; i < nodes.size(); ++i) {
if (nodes[i].val == val) {
nodes.erase(nodes.begin() + i);
break;
}
}
}
// 删除边
void deleteEdge(int src, int dst) {
for (int i = 0; i < nodes[src].neighbors.size(); ++i) {
if (nodes[src].neighbors[i] == dst) {
nodes[src].neighbors.erase(nodes[src].neighbors.begin() + i);
break;
}
}
for (int i = 0; i < nodes[dst].neighbors.size(); ++i) {
if (nodes[dst].neighbors[i] == src) {
nodes[dst].neighbors.erase(nodes[dst].neighbors.begin() + i);
break;
}
}
}
// 遍历顶点
void traverse() {
for (auto& node : nodes) {
cout << node.val << ": ";
for (auto neighbor : node.neighbors) {
cout << neighbor << " ";
}
cout << endl;
}
}
private:
vector<GraphNode> nodes; // 存储所有顶点
};
int main() {
Graph graph;
graph.addNode(0);
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.traverse();
graph.deleteNode(2);
graph.traverse();
graph.deleteEdge(0, 1);
graph.traverse();
return 0;
}
```
使用邻接矩阵实现图的基本操作的C++代码示例与邻接表类似,只是数据结构不同。