编写一个c++程序,使用广度优先遍历的方式遍历一个无向图,并输出遍历序列,要求使用邻接表存储无向图。
时间: 2024-12-26 10:29:15 浏览: 1
在C++中,你可以使用队列数据结构来实现广度优先搜索(Breadth-First Search, BFS)算法来遍历无向图。这里我们假设你已经有了一个邻接表表示的无向图,每个顶点都是一个节点,而边则是连接两个节点的数据结构。下面是一个简单的例子:
```cpp
#include <iostream>
#include <queue>
#include <vector>
// 定义一个节点结构
struct Node {
int id;
std::vector<int> neighbors; // 邻居列表
};
// 广度优先遍历函数
void bfs(Node* graph[], int start, std::vector<int>& visited) {
std::queue<Node*> q;
q.push(graph[start]);
visited[start] = 1;
while (!q.empty()) {
Node* curr = q.front();
q.pop();
std::cout << curr->id << " "; // 输出当前节点
for (int neighbor : curr->neighbors) { // 遍历邻居
if (!visited[neighbor]) { // 如果未访问过
visited[neighbor] = 1; // 标记为已访问
q.push(graph[neighbor]); // 入队
}
}
}
}
int main() {
Node graph[] = { ... }; // 初始化你的邻接表数组
int numVertices = sizeof(graph) / sizeof(Node); // 获取节点数
std::vector<int> visited(numVertices, 0); // 初始化访问标记
// 使用BFS遍历并输出路径
bfs(graph, 0, visited);
return 0;
}
```
在这个示例中,`graph[]`是存储无向图的邻接表,`start`是你想要从哪个节点开始遍历。`bfs()`函数会从给定的起始节点开始,逐层遍历图,直到所有可达节点都被访问。
阅读全文