C++代码完整实现建立无向图的邻接表存储结构,将邻接表输出,分别进行无向图的深度优先搜索遍历和广度优先搜索遍历。
时间: 2025-01-05 10:37:14 浏览: 17
在C++中,我们可以使用邻接表来存储无向图的数据结构。首先,我们需要定义节点(Node)和边(Edge),然后创建邻接表数组表示每个顶点的邻居。以下是基本的代码实现:
```cpp
#include <iostream>
#include <vector>
// 定义节点类
class Node {
public:
int id;
std::vector<int> neighbors; // 邻居列表
Node(int id) : id(id) {}
};
// 创建无向图类
class Graph {
private:
std::vector<Node*> vertices; // 存储所有节点的邻接表
public:
void add_edge(int src, int dest) {
Node* src_node = find_vertex(src);
if (src_node == nullptr)
vertices.push_back(new Node(src));
src_node->neighbors.push_back(dest);
Node* dest_node = find_vertex(dest);
if (dest_node == nullptr)
vertices.push_back(new Node(dest));
dest_node->neighbors.push_back(src); // 添加双向连接
}
// 搜索并返回节点
Node* find_vertex(int id) {
for (Node* node : vertices)
if (node->id == id)
return node;
return nullptr;
}
// 输出邻接表
void print_neighbors() {
for (const auto& node : vertices) {
std::cout << "Node " << node->id << ": ";
for (int neighbor : node->neighbors)
std::cout << neighbor << " ";
std::cout << "\n";
}
}
// 深度优先搜索
void dfs(int start) {
std::vector<bool> visited(vertices.size(), false);
dfs_helper(start, visited);
}
void dfs_helper(int vertex, std::vector<bool>& visited) {
visited[vertex] = true;
std::cout << vertex << " ";
for (int neighbor : vertices[vertex]->neighbors)
if (!visited[neighbor])
dfs_helper(neighbor, visited);
}
// 广度优先搜索
void bfs(int start) {
std::vector<bool> visited(vertices.size(), false);
std::queue<int> queue;
queue.push(start);
while (!queue.empty()) {
int current = queue.front();
queue.pop();
visited[current] = true;
std::cout << current << " ";
for (int neighbor : vertices[current]->neighbors)
if (!visited[neighbor])
queue.push(neighbor);
}
}
};
int main() {
Graph graph;
// 添加边和节点...
graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(2, 3);
graph.add_edge(3, 4);
graph.print_neighbors(); // 输出邻接表
graph.dfs(0); // 深度优先搜索
graph.bfs(0); // 广度优先搜索
return 0;
}
```
在这个代码里,我们首先创建了一个`Graph`类,包含添加节点、添加边、查找节点、打印邻接表以及深度优先搜索(DFS)和广度优先搜索(BFS)的方法。请注意,你需要自行补充添加节点、边以及实际运行搜索的部分。
阅读全文