可以拿C++实现是什么样的吗
时间: 2024-12-18 07:26:57 浏览: 3
当然可以,下面是使用C++实现无向邻接图(Adjacency List)的一个简单示例,这里我们使用了`std::list`作为链表数据结构:
```cpp
#include <iostream>
#include <unordered_map>
#include <list>
// 定义顶点和边的数据结构
struct Vertex {
int id;
std::list<Vertex*> adjacents; // 存储邻接顶点
};
class Graph {
private:
std::unordered_map<int, Vertex> vertices; // 通过顶点id查找对应的顶点
public:
void addEdge(int src, int dest) {
if (vertices.find(src) == vertices.end()) {
vertices[src] = {src}; // 初始化新顶点
}
if (vertices.find(dest) == vertices.end()) {
vertices[dest] = {dest};
}
// 添加边:将目标顶点加入源顶点的邻接列表
vertices[src].adjacents.push_back(&vertices[dest]);
// 自反边,如果需要的话,也可以将源顶点加入目标顶点的邻接列表
vertices[dest].adjacents.push_back(&vertices[src]);
}
// 其他操作...
};
int main() {
Graph g;
g.addEdge(0, 1); // 添加边0->1
g.addEdge(1, 2); // 添加边1->2
// 更多边...
return 0;
}
```
在这个例子中,`addEdge`函数会检查给定的顶点是否已存在,并将其添加到图中。然后,它会在源顶点的邻接列表中添加目标顶点,形成无向边。注意,这里为了简单起见,只处理了一个方向的边,如果你需要双向连接,则需要在推入源顶点到目标顶点邻接列表的同时,也将目标顶点加入源顶点的邻接列表。
阅读全文