请提供一个由C++编写的BFS模板
时间: 2023-06-06 20:07:41 浏览: 88
以下是由C编写的BFS模板:
```C
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000 //最大节点数
struct Queue{
int data[MAX_N]; //存储节点编号
int head; //队头指针
int tail; //队尾指针
};
int n; //节点总数
int m; //边总数
int visited[MAX_N]; //记录节点是否被访问过
int graph[MAX_N][MAX_N]; //用邻接矩阵存储图
struct Queue queue; //定义队列
void BFS(int start){
visited[start] = 1; //标记起点被访问过
queue.head = 0; //初始化队列
queue.tail = 0;
queue.data[queue.tail++] = start; //将起点加入队列
while (queue.head < queue.tail){ //队列非空时循环
int node = queue.data[queue.head++]; //取出队头节点
printf("%d ", node); //输出节点编号
for (int i = 0; i < n; i++){ //遍历与该节点相邻的节点
if (graph[node][i] && !visited[i]){ //未访问过且有连边
visited[i] = 1; //标记该节点被访问过
queue.data[queue.tail++] = i; //将该节点加入队列
}
}
}
}
int main(){
scanf("%d%d", &n, &m); //读入节点总数和边总数
//初始化图
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
graph[i][j] = 0; //先全部标记为不可达
}
}
//读入每条边
for (int i = 0; i < m; i++){
int u, v;
scanf("%d%d", &u, &v);
graph[u][v] = graph[v][u] = 1; //标记为可达
}
//从节点0开始进行BFS
BFS(0);
return 0;
}
```
阅读全文