BFS是无权图最短路径的最优解法，因其按层扩展可保证首次抵达终点时路径长度最小；需用队列、距离数组（或哈希映射）、访问标记实现，支持路径还原与多源扩展。
如果您需要在无权图中找到从起点到终点的最短路径，广度优先搜索（BFS）是天然适配的算法，因其按层扩展的特性可保证首次抵达终点时路径长度最小。以下是多种可行的C++实现方法：
一、标准邻接表 + queue + 距离数组
该方法使用vector
1、声明图结构：定义vector
2、构建邻接表：对每条无向边(u, v)，执行graph[u].push_back(v)和graph[v].push_back(u)；
3、初始化距离数组：vector
4、创建队列并入队起点：queue
5、循环处理队列：当q非空时，取队首u，遍历graph[u]中每个v；
6、若dist[v] == -1，则设置dist[v] = dist[u] + 1，并q.push(v)；
7、当u等于end时，立即返回dist[u]，此时值即为最短路径长度。
二、坐标网格 + 方向数组 + 边界检查
适用于二维网格类图（如迷宫），将每个格子视为节点，用dx/dy数组枚举上下左右四个移动方向，通过边界与障碍物双重校验控制合法转移。
1、定义方向偏移量：int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}；
2、声明距离二维数组：vector
3、设置起点距离：dist[start_r][start_c] = 0，入队pair
4、每次出队后，尝试四个方向：new_r = curr.first + dx[i], new_c = curr.second + dy[i]；
5、检查new_r与new_c是否在[0, r)和[0, c)范围内且grid[new_r][new_c]为通行状态；
6、若dist[new_r][new_c] == -1，则更新dist[new_r][new_c] = dist[curr.first][curr.second] + 1，并入队；
7、当new_r == end_r且new_c == end_c时，直接返回当前新距离值。
三、路径还原版 —— 维护parent数组
在记录最短距离的同时，用parent数组保存每个节点的前驱节点，支持反向重构完整最短路径，适用于需输出具体路径而非仅长度的场景。
1、声明parent数组：vector
2、入队邻居v前，设置parent[v] = u；
3、到达end后不立即返回，继续完成BFS或提前break；
4、从end开始沿parent回溯：vector
5、反转path后得到从start到end的最短路径节点序列；
6、路径长度即为path.size() - 1，该序列中相邻节点必为图中真实存在的边。
四、节点编号稀疏时的哈希映射方案
当输入节点编号不连续（如仅含{1001, 5007, 9999}）且总数不大时，避免申请超大数组，改用unordered_map
1、声明映射：unordered_map
2、初始化起点：dist[start] = 0, parent[start] = start；
3、使用queue
4、对每个出队节点u，遍历其邻接节点v；
5、若dist.count(v) == 0，则dist[v] = dist[u] + 1，parent[v] = u，q.push(v)；
6、当v等于end时，dist[end]即为最短距离，无需额外循环。
五、多源BFS扩展 —— 同时从多个起点出发
用于求解“所有起点中离某点最近的距离”或“多工厂覆盖范围”等场景，将全部起点一次性入队并设dist为0，其余逻辑与单源一致，天然支持并行层扩展。
1、准备起点集合：vector
2、初始化dist数组全为-1，对每个si设置dist[si] = 0并q.push(si)；
3、BFS主循环中，每次出队u后遍历其邻居v；
4、若dist[v] == -1，则dist[v] = dist[u] + 1，q.push(v)；
5、当首次访问到target时，dist[target]即为所有起点出发能到达它的最短距离。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
