void BFS(AMGraph G,int v,int Bf[]) { SqQueue Q; int I=0,u; InitQueue(Q); visited[v]=1; Bf[I++]=v; EnQueue(Q,v);下面的完整代码
时间: 2023-10-19 07:07:23 浏览: 106
C# 广度优先遍历(BFS)算法实现
5星 · 资源好评率100%
好的,下面是完整的代码,包括图的建立函数和BFS遍历函数:
```c++
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100;
int G[MAXN][MAXN]; // 图的邻接矩阵存储
int visited[MAXN]; // 标记数组,记录每个顶点是否已被访问
int n, m; // n为结点数,m为边数
void createGraph() {
memset(G, 0, sizeof(G)); // 初始化邻接矩阵
cin >> n >> m;
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v;
G[u][v] = G[v][u] = 1; // 无向图,边是双向的
}
}
void BFS(int v, int Bf[]) { // 广度优先搜索
queue<int> Q;
int I = 0, u;
memset(visited, 0, sizeof(visited)); // 初始化visited数组
visited[v] = 1;
Bf[I++] = v;
Q.push(v);
while (!Q.empty()) {
u = Q.front();
Q.pop();
for (int i = 0; i < n; i++) {
if (G[u][i] && !visited[i]) { // 如果u和v之间有边,且v未被访问过
visited[i] = 1;
Bf[I++] = i;
Q.push(i);
}
}
}
}
int main() {
createGraph(); // 建立图
int s; // 广搜起点
cin >> s;
int Bf[MAXN]; // 广搜序列
BFS(s, Bf);
for (int i = 0; i < n; i++) {
cout << Bf[i] << " ";
}
cout << endl;
return 0;
}
```
在该程序中,我们新增了一个Bf数组,用于存储广搜序列。在BFS函数中,我们将Bf数组作为参数传入,每当一个顶点被访问时,就将其加入Bf数组中。最后在主函数中输出Bf数组即可。
阅读全文