能否提供一个用C++实现的邻接矩阵和邻接表数据结构的详细代码示例?
时间: 2024-11-15 22:28:38 浏览: 13
当然可以。在C++中,邻接矩阵和邻接表都是用于表示图的数据结构。
**邻接矩阵**:
```cpp
#include <vector>
// 定义一个二维数组作为邻接矩阵
class AdjacencyMatrix {
public:
int V; // 顶点数
std::vector<std::vector<int>> adj; // 邻接矩阵
// 构造函数
AdjacencyMatrix(int v) : V(v), adj(v, std::vector<int>(v, 0)) {}
// 添加边 (u, v)
void addEdge(int u, int v) {
adj[u][v] = 1; // 如果(u, v)是一条边,则置其值为1
}
// 检查是否存在边 (u, v)
bool isEdge(int u, int v) {
return adj[u][v] != 0;
}
};
```
**邻接表**:
```cpp
#include <list>
#include <vector>
// 使用std::list存储邻居列表
class AdjacencyList {
public:
int V; // 顶点数
std::vector<std::list<int>> adj; // 存储邻接表
// 构造函数
AdjacencyList(int v) : V(v), adj(v) {}
// 添加边 (u, v)
void addEdge(int u, int v) {
adj[u].push_back(v); // 将v添加到u的邻居列表中
}
// 检查是否存在边 (u, v)
bool isEdge(int u, int v) {
return find(adj[u], v) != adj[u].end(); // 如果v在u的邻居列表中返回true
}
private:
// 使用内置查找算法找到元素
template<typename T>
typename std::list<T>::iterator find(std::list<T>& list, const T& value) {
return std::find(list.begin(), list.end(), value);
}
};
```
阅读全文