广度优先遍历连通图c++代码
时间: 2023-06-23 21:56:16 浏览: 47
以下是广度优先遍历连通图的C++代码实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大
vector<int> adj[MAXN]; // 邻接表
bool visited[MAXN]; // 标记数组
void BFS(int s) {
queue<int> q; // 定义队列
visited[s] = true; // 标记s已访问
q.push(s); // 将s入队
while (!q.empty()) { // 队列不为空
int u = q.front(); // 取出队首元素
q.pop(); // 将队首元素出队
cout << u << " "; // 输出u
for (int v : adj[u]) { // 遍历u的所有邻接点
if (!visited[v]) { // 如果v未被访问
visited[v] = true; // 标记v已访问
q.push(v); // 将v入队
}
}
}
}
int main() {
int n, m; // n为顶点数,m为边数
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v; // u和v之间有一条边
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u); // 无向图需要加上这一行
}
int s; // 指定起点
cin >> s;
BFS(s); // 从s开始遍历
return 0;
}
```
该算法的时间复杂度为$O(|V|+|E|)$,其中$|V|$和$|E|$分别为顶点数和边数。因为每个顶点和每条边都只会被访问一次。