用c++写一个bfs算法
时间: 2024-04-29 21:25:05 浏览: 11
好的,以下是使用 C 语言写的 BFS(广度优先搜索)算法示例代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000 // 最大顶点数
int n, m; // n 代表顶点数,m 代表边数
int e[MAXN][MAXN]; // 边的邻接矩阵
int vis[MAXN]; // 标记数组,用于标记某个顶点是否已经被遍历过
typedef struct {
int data[MAXN]; // 存储某一层节点的编号
int length; // 存储某一层节点的数量
} Queue;
void enqueue(Queue *q, int x) {
q->data[q->length++] = x;
}
int dequeue(Queue *q) {
if (q->length == 0) {
return -1; // 当队列为空时返回 -1
}
int x = q->data[0];
for (int i = 0; i < q->length - 1; i++) {
q->data[i] = q->data[i + 1];
}
q->length--;
return x;
}
void bfs(int u) {
Queue q1, q2; // 定义两个队列,分别用于存储当前层和下一层的顶点
// 初始化队列,并将当前顶点 u 入队
q1.length = 0;
q2.length = 0;
memset(vis, 0, sizeof(vis));
vis[u] = 1;
enqueue(&q1, u);
while (1) {
// 当前层已经遍历完
if (q1.length == 0) {
break;
}
int x = dequeue(&q1); // 取出队头元素
printf("%d ", x); // 处理当前顶点
// 将下一层顶点入队
for (int i = 1; i <= n; i++) {
if (e[x][i] == 1 && vis[i] == 0) {
vis[i] = 1;
if (q1.length > 0) {
enqueue(&q1, i);
} else {
enqueue(&q2, i);
}
}
}
// 当前层已经遍历完
if (q1.length == 0) {
// 切换到下一层,并清空队列
Queue tmp = q1;
q1 = q2;
q2 = tmp;
}
}
}
int main() {
scanf("%d %d", &n, &m);
memset(e, 0, sizeof(e)); // 将邻接矩阵清空
// 读入边
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
e[u][v] = 1; // 标记边
e[v][u] = 1; // 无向图需要标记另外一条边
}
bfs(1); // 从第一个顶点开始遍历
return 0;
}
```
希望对您有帮助!