图的广度优先遍历c++程序
时间: 2023-06-23 14:46:08 浏览: 46
以下是一个基于邻接矩阵的图的广度优先遍历的 C++ 程序。
```c++
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100;
int n, m; // n 个节点,m 条边
bool g[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 记录节点是否已访问
void bfs(int u) {
queue<int> q;
q.push(u);
visited[u] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int i = 0; i < n; i++) {
if (g[v][i] && !visited[i]) {
q.push(i);
visited[i] = true;
}
}
}
}
int main() {
cin >> n >> m;
// 读入边
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u][v] = g[v][u] = true;
}
// 从每个未被访问的节点开始 bfs
for (int i = 0; i < n; i++) {
if (!visited[i]) {
bfs(i);
}
}
return 0;
}
```
该程序首先读入图的边,然后从每个未被访问的节点开始进行广度优先遍历,遍历过程中使用一个队列来存储已经访问但还未被遍历的节点。每次从队列中取出一个节点,输出它的编号,然后将其所有未被访问的邻居节点加入队列中。遍历结束后,所有节点都被访问且每个节点都被输出了一次。