BFS在无权图中找最短路径的核心是：队列存节点及当前距离，首次访问终点时的距离即最短；需用邻接表建图（无向图双向加边），初始化dist数组，按层遍历保证正确性。
用 BFS 在无权图中找最短路径，核心就一条：队列里存节点+距离，第一次访问到终点时的距离就是最短。邻接表建图、std::queue 或手写循环队列都行，但别用 std::vector 模拟队列——出队是 O(n)，会拖慢整个搜索。
怎么用邻接表存图并保证 BFS 正确遍历
邻接表本质是「每个节点对应一个边列表」，C++ 推荐用 vector<vector>></vector> 或 vector<list>></list>；如果要存带权边（哪怕权值恒为 1），就用 vector<vector int>>></vector>。注意：无向图必须双向加边，漏掉一边会导致部分节点不可达。
- 建图前先初始化
graph.resize(n)，n 是节点总数（0-indexed） - 添加边用
graph[u].push_back(v)，无向图再补一句graph[v].push_back(u) - 不要在 BFS 过程中动态修改
graph，否则可能破坏遍历顺序或引发迭代器失效
队列里到底该存什么数据
只存节点编号（int）够用，但必须配套维护一个 dist[] 数组记录起点到各点的最短距离。更稳妥的做法是队列直接存 pair<int int></int>（节点编号，当前距离），避免数组读写竞争或初始化疏漏。
- 起始点入队前设
dist[start] = 0，其余初始化为 -1 或INT_MAX - 每次从队列取节点
u后，只更新未访问过的邻居v：若dist[v] == -1，则dist[v] = dist[u] + 1并入队 - 一旦
v == target，立刻返回dist[v]，无需等队列清空
为什么 BFS 找到的第一个终点就是最短路径
因为 BFS 按层展开，每层节点到起点的边数相同。第 k 层所有节点的 dist 值都是 k。所以第一次碰到终点，一定是在它所属的最小层数上——这个性质只在边权相等（或全为 1）时成立。
立即学习“C++免费学习笔记（深入）”；
- 如果图有权重且不全相等，必须换
Dijkstra，不能硬套BFS - 如果节点数极大（比如 1e5）、边稀疏，邻接表 +
queue时间复杂度是O(V + E)，比邻接矩阵省空间也更快 - 用
bool visited[]替代dist[] != -1判断也可，但丢失距离信息，无法回溯路径
真正容易卡住的地方不是写不出循环，而是忘记初始化 dist 数组、搞混有向/无向边方向、或者在多组测试时复用队列却没清空。最短路径本身不存路径点序列的话，连 prev[] 数组都不用开——轻量场景下，4 行核心逻辑就能跑通。
