图的BFS使用邻接矩阵使用队列模板实现
时间: 2024-05-07 12:18:43 浏览: 9
以下是使用邻接矩阵和队列模板实现BFS的代码:
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大节点数
int G[MAXN][MAXN]; // 存储邻接矩阵
bool vis[MAXN]; // 记录节点是否被访问过
void bfs(int s, int n) // s为起点,n为节点数
{
queue<int> q; // 定义队列
q.push(s); // 起点入队
vis[s] = true; // 标记起点已访问
while (!q.empty())
{
int u = q.front(); // 取出队首节点
q.pop(); // 弹出队首节点
cout << u << " "; // 访问节点
for (int v = 0; v < n; v++) // 遍历与u相邻的节点
{
if (G[u][v] && !vis[v]) // 如果v与u相邻且未被访问过
{
q.push(v); // v入队
vis[v] = true; // 标记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][v] = G[v][u] = 1; // 无向图
}
bfs(0, n); // 从节点0开始BFS
return 0;
}
```
其中,`vis`数组用于记录节点是否被访问过,初始值为`false`。队列`q`用于存储需要遍历的节点,初始时将起点`s`入队,然后进行循环,每次取出队首节点`u`,访问它,然后遍历与它相邻的节点`v`,如果`v`未被访问过,则将其入队,并标记为已访问。循环结束后,BFS遍历就完成了。