用C++写一个BFS算法
时间: 2023-05-27 17:07:27 浏览: 100
以下是C语言实现的BFS算法示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 //图中最大顶点数
//定义邻接矩阵结构体
typedef struct {
int vertex[MAX_VERTEX_NUM];
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vertex_num;
int edge_num;
} Graph;
//初始化图
void initGraph(Graph* g, int n) {
g->vertex_num = n;
g->edge_num = 0;
for(int i=0; i<MAX_VERTEX_NUM; i++) {
g->vertex[i] = 0;
for(int j=0; j<MAX_VERTEX_NUM; j++) {
g->edge[i][j] = 0;
}
}
}
//添加边
void addEdge(Graph* g, int u, int v) {
g->edge[u][v] = 1;
g->edge[v][u] = 1;
g->edge_num++;
}
//BFS算法
void BFS(Graph* g, int start) {
int visited[MAX_VERTEX_NUM] = {0}; //标记数组,初始状态下所有顶点都未被访问
int queue[MAX_VERTEX_NUM] = {0}; //队列,用于存储待访问的顶点
int front = 0, rear = 0; //队列的首尾指针
visited[start] = 1; //标记起始顶点已被访问
queue[rear++] = start; //将起始顶点入队
while(front < rear) { //队列不为空时循环
int cur = queue[front++]; //取出队首元素
printf("%d ", cur); //访问该顶点
//遍历该顶点的所有邻接顶点,将未被访问的顶点入队
for(int i=0; i<g->vertex_num; i++) {
if(g->edge[cur][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
}
int main() {
Graph g;
int n, m;
printf("请输入顶点数和边数:");
scanf("%d %d", &n, &m);
initGraph(&g, n);
printf("请输入每条边的两个端点:\n");
for(int i=0; i<m; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(&g, u, v);
}
printf("BFS遍历结果:");
BFS(&g, 0);
printf("\n");
return 0;
}
```
在上述示例中,我们首先定义了一个邻接矩阵结构体Graph,包含了顶点数组、边数组、顶点数和边数等信息。然后,我们实现了初始化图、添加边、BFS算法等几个函数。最后,在main函数中读入图的信息,调用BFS函数进行遍历。
BFS函数的主要思路是,从起点开始,将其加入队列,并标记为已访问。然后,循环取出队首元素,访问该顶点,并将其所有未被访问的邻接顶点加入队列,并标记为已访问。直到队列为空为止。
阅读全文