int a,b; G.vexnum=n; G.arcnum=m; //memset(G.arcs,0,sizeof(G.arcs)); for(int i=0;i<G.vexnum;i++) for(int j=0;j<G.vexnum;j++) G.arcs[i][j]=0; for(int i=0;i<G.arcnum;i++) { a=bian[i].v1; b=bian[i].v2; G.arcs[a][b]=G.arcs[b][a]=1; } } 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);下面的代码
时间: 2024-01-21 16:05:01 浏览: 87
好的,根据上下文信息,这里是一个无向图的邻接矩阵存储方式的BFS遍历算法。下面是完整的代码:
```c++
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100;
int visited[MAXN]; // 标记数组,记录每个顶点是否已被访问
typedef struct {
int v1, v2;
} Bian; // 边结构体
typedef struct {
int arcs[MAXN][MAXN]; // 存储邻接矩阵
int vexnum, arcnum; // 结点数和边数
} AMGraph; // 图结构体
void createGraph(AMGraph &G, Bian bian[], int n, int m) { // 建立无向图的邻接矩阵存储
int a, b;
G.vexnum = n;
G.arcnum = m;
memset(G.arcs, 0, sizeof(G.arcs)); // 初始化邻接矩阵
for (int i = 0; i < G.arcnum; i++) {
a = bian[i].v1;
b = bian[i].v2;
G.arcs[a][b] = G.arcs[b][a] = 1; // 无向图,边是双向的
}
}
void BFS(AMGraph G, 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 < G.vexnum; i++) {
if (G.arcs[u][i] && !visited[i]) { // 如果u和v之间有边,且v未被访问过
visited[i] = 1;
Bf[I++] = i;
Q.push(i);
}
}
}
}
int main() {
int n, m; // n为结点数,m为边数
cin >> n >> m;
Bian bian[m];
int v; // 广搜起点
cin >> v;
int Bf[MAXN]; // 广搜序列
for (int i = 0; i < m; i++) {
cin >> bian[i].v1 >> bian[i].v2;
}
AMGraph G;
createGraph(G, bian, n, m); // 建立图
BFS(G, v, Bf);
for (int i = 0; i < n; i++) {
cout << Bf[i] << " ";
}
cout << endl;
return 0;
}
```
在该程序中,我们新加了一个结构体Bian,用于存储边的信息。在createGraph函数中,我们将边数组bian作为参数传入,遍历边数组,将每条边的两个顶点在邻接矩阵中标记为有边相连。最后,在主函数中输入结点数、边数、边的信息和广搜起点,建立图后调用BFS函数进行广搜遍历,并输出广搜序列。
阅读全文