用C++写广度优先搜索算法,每行都要配上解释
时间: 2024-06-11 17:04:06 浏览: 9
以下是C语言实现广度优先搜索算法的代码,附带注释解释每一行的功能。
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100 // 定义队列的最大容量
int visited[MAX_QUEUE_SIZE]; // 标记已访问的节点,避免重复遍历
int queue[MAX_QUEUE_SIZE]; // 定义队列
int front = -1; // 队首
int rear = -1; // 队尾
int graph[MAX_QUEUE_SIZE][MAX_QUEUE_SIZE]; // 用邻接矩阵表示图
void bfs(int start, int n); // 广度优先搜索函数
int main()
{
int n, start; // n为节点数,start为起始节点
printf("请输入节点数:");
scanf("%d", &n);
// 输入图的邻接矩阵
printf("请输入图的邻接矩阵:\n");
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
scanf("%d", &graph[i][j]);
}
}
printf("请输入起始节点:");
scanf("%d", &start);
bfs(start, n); // 进行广度优先搜索
return 0;
}
void bfs(int start, int n)
{
visited[start] = 1; // 标记起始节点已访问
queue[++rear] = start; // 将起始节点入队
while(front != rear){ // 当队列不为空时
int cur = queue[++front]; // 取出队首元素
printf("%d ", cur); // 输出当前节点
for(int i = 0; i < n; i++){
if(graph[cur][i] && !visited[i]){ // 如果当前节点与i节点有连边且i节点未被访问
visited[i] = 1; // 标记i节点已访问
queue[++rear] = i; // 将i节点入队
}
}
}
}
```
注释解释:
第 3 行:定义队列的最大容量为100。
第 5 行:定义一个数组 visited,用于标记已访问的节点。
第 6 行:定义一个数组 queue,用于存储待访问的节点。
第 7 行和第 8 行:分别定义队首和队尾的初始值为 -1。
第 10 行:定义一个二维数组 graph,用邻接矩阵表示图。
第 12 行:定义函数 bfs,用于实现广度优先搜索。
第 23 行:标记起始节点已访问。
第 24 行:将起始节点入队。
第 26 行:当队列不为空时,循环执行以下操作。
第 27 行:取出队首元素。
第 28 行:输出当前节点。
第 30 行:遍历当前节点的所有邻居。
第 31 行:如果当前节点与 i 节点有连边且 i 节点未被访问,执行以下操作。
第 32 行:标记 i 节点已访问。
第 33 行:将 i 节点入队。