广度优先搜索是一种逐层遍历图的算法，核心思想是从起始节点开始，先访问所有距离起始节点为1的节点，再访问距离为2的节点，以此类推，直到找到目标节点或者遍历完所有可达节点。由于它是按距离从小到大的顺序访问节点，所以第一次找到目标节点时的路径就是最短路径。
BFS与队列的关联
队列是BFS实现的核心数据结构，因为BFS需要按照节点被访问的顺序依次处理后续的邻接节点，而队列先进先出的特性刚好符合这个需求。我们把起始节点放入队列，每次从队列头部取出节点，将其未访问过的邻接节点放入队列尾部，同时记录这些邻接节点的距离，就能保证按距离从小到大的顺序遍历所有节点。
核心实现步骤
- 定义图的结构，这里用邻接表表示无向图
- 创建队列存储待访问的节点，创建数组记录节点是否被访问过，创建数组记录每个节点到起始节点的距离
- 将起始节点入队，标记已访问，距离设为0
- 循环处理队列中的节点，取出队首节点，遍历其所有邻接节点，若邻接节点未被访问，则标记已访问，更新距离，入队，若邻接节点是目标节点则结束循环
- 最终目标节点的距离就是最短路径长度
完整代码实现
以下代码实现了用BFS查找无向图中两个节点之间的最短路径，假设图的节点编号从0开始：
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
// 用邻接表存储图
vector<int> graph[100];
// 标记节点是否被访问
bool visited[100];
// 记录节点到起始节点的距离
int distance[100];
// BFS查找最短路径，返回起始节点到目标节点的最短距离，若不可达返回-1
int bfs_shortest_path(int start, int target, int node_num) {
// 初始化访问标记和距离数组
memset(visited, false, sizeof(visited));
memset(distance, -1, sizeof(distance));
queue<int> q;
// 起始节点入队
q.push(start);
visited[start] = true;
distance[start] = 0;
while (!q.empty()) {
int current = q.front();
q.pop();
// 如果当前节点是目标节点，直接返回距离
if (current == target) {
return distance[current];
}
// 遍历当前节点的所有邻接节点
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
distance[neighbor] = distance[current] + 1;
q.push(neighbor);
}
}
}
// 遍历完所有可达节点仍未找到目标节点，返回-1
return -1;
}
int main() {
// 示例：构建有5个节点的无向图
int node_num = 5;
// 添加边：0-1, 0-2, 1-3, 2-3, 3-4
graph[0].push_back(1);
graph[1].push_back(0);
graph[0].push_back(2);
graph[2].push_back(0);
graph[1].push_back(3);
graph[3].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
graph[3].push_back(4);
graph[4].push_back(3);
int start = 0;
int target = 4;
int shortest_path = bfs_shortest_path(start, target, node_num);
if (shortest_path != -1) {
cout << "从节点" << start << "到节点" << target << "的最短路径长度为：" << shortest_path << endl;
} else {
cout << "节点" << start << "到节点" << target << "不可达" << endl;
}
return 0;
}
代码逻辑解析
上述代码中，graph数组用来存储图的邻接关系，每个索引对应一个节点，数组元素是该节点的所有邻接节点列表。visited数组用来避免重复访问节点，防止进入死循环。distance数组用来记录每个节点到起始节点的最短距离，初始化为-1表示未访问。
在bfs_shortest_path函数中，首先将起始节点入队，然后循环处理队列中的节点。每次取出队首节点后，先判断是否是目标节点，如果是就直接返回距离。如果不是，就遍历它的所有邻接节点，将未访问过的邻接节点标记已访问，更新距离，然后入队。这样就能保证所有节点都是按距离从小到大的顺序被访问，第一次找到目标节点时的距离就是最短路径长度。
注意事项
- 该实现适用于无权图，如果是带权图，BFS无法保证找到的是最短路径，需要使用Dijkstra等算法
- 图的节点数量需要根据实际情况调整，上述代码默认最大节点数为100，若节点更多可以修改数组大小或者使用动态容器
- 如果图是有向图，只需要调整邻接表的添加方式，不需要添加反向边即可
- 队列中存储的是节点编号，距离通过单独的数组记录，避免队列存储过多冗余信息