使用C++STL实现BFS
时间: 2023-07-11 19:39:49 浏览: 77
以下是使用C++ STL实现BFS的示例代码:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记顶点是否访问过
void bfs(int s) {
queue<int> q;
q.push(s);
vis[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
int main() {
int n, m; // n 表示顶点数,m 表示边数
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u); // 无向图需要反向建边
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
bfs(i);
}
}
return 0;
}
```
该代码实现了一个简单的无向图的BFS遍历,使用了STL中的queue和vector容器,其中queue用于存储待访问的节点,vector用于存储图的邻接表。BFS遍历的核心逻辑在bfs函数中实现,该函数首先将起点压入队列,然后依次从队列中取出每个节点,访问该节点,并将其未访问过的邻居节点压入队列。在主函数中,我们遍历每个顶点,如果该顶点未访问过,则从该顶点开始进行BFS遍历。