按照算法导论中bfs算法,写出其C++代码
时间: 2024-04-27 07:02:45 浏览: 9
以下是基于邻接表表示的无向图的BFS算法的C++代码:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 100010;
vector<int> adj[N]; // 邻接表
bool vis[N]; // 标记是否被访问过
void bfs(int u) {
queue<int> q;
q.push(u);
vis[u] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int i = 0; i < adj[v].size(); i++) {
int w = adj[v][i];
if (!vis[w]) {
vis[w] = true;
q.push(w);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
bfs(i);
}
}
return 0;
}
```
其中,`adj[i]` 表示与节点i相邻的节点的列表,`vis[i]` 表示节点i是否被访问过。在BFS算法中,首先将起始节点加入队列,并将其标记为已访问。然后不断从队列中取出节点,访问该节点,并将其未访问过的邻居加入队列中,直到队列为空。在具体实现中,使用STL库中的queue来存储队列,并使用vector来表示邻接表。