编写一个c++程序,用邻接表存储有向图,并输出该邻接表,最后编写主函数进行测试。
时间: 2024-12-26 11:28:33 浏览: 8
在C++中,我们可以使用`std::vector`作为邻接表的数据结构来存储有向图。下面是一个简单的示例,包括如何创建邻接表、添加边以及输出邻接表:
```cpp
#include <iostream>
#include <vector>
// 定义邻接表节点结构
struct Node {
int id;
std::vector<int> neighbors; // 存储邻居节点的列表
};
// 邻接表表示有向图
class AdjacencyListGraph {
private:
std::vector<Node> nodes;
public:
void addNode(int id) {
nodes.push_back({id, {}});
}
void addEdge(int src, int dst) {
for (auto &node : nodes) {
if (node.id == src) {
node.neighbors.push_back(dst);
break; // 只在一个源节点上添加边
}
}
}
// 输出邻接表
void printAdjList() {
for (const auto &node : nodes) {
std::cout << "Node ID: " << node.id << ", Neighbors: ";
for (int neighbor : node.neighbors) {
std::cout << neighbor << " ";
}
std::cout << "\n";
}
}
// 主函数测试
static void mainFunction() {
AdjacencyListGraph graph;
graph.addNode(0); // 添加节点
graph.addNode(1);
graph.addNode(2);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.printAdjList(); // 输出邻接表
}
};
```
在这个例子中,我们首先定义了一个`Node`结构体,用于存储每个节点及其邻居。然后,我们在`AdjacencyListGraph`类中实现了添加节点、添加边和打印邻接表的功能。在`mainFunction`中,我们创建了一个有向图实例并添加了一些边,最后调用`printAdjList`来展示邻接表。
阅读全文