图的邻接表的广度优先搜索c++
时间: 2023-11-05 08:58:35 浏览: 50
以下是图的邻接表的广度优先搜索的C++代码:
```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 << " "; // 输出节点u
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v); // 添加边
G[v].push_back(u);
}
bfs(s); // 从起点s开始广度优先搜索
return 0;
}
```
其中,`n`为节点数,`m`为边数,`s`为起点。`G[u].push_back(v)`表示从节点`u`到节点`v`添加一条无向边。在广度优先搜索时,我们使用队列来存储待访问的节点,每次访问一个节点时,将其所有未访问的邻居加入队列中。`vis`数组用于记录节点是否被访问过。