队列中只存顶点编号int，距离用独立dist[]数组维护，避免混入距离导致更新混乱；邻接矩阵BFS时间复杂度为O(V²)，因每次需扫描整行找邻接点。
用邻接矩阵实现 BFS 时，队列里该存什么？
别存 pair<int, int> 或带距离的结构体——除非你真需要每步的路径长度。多数场景下，只存顶点编号 int 就够了，距离用单独数组 dist[] 维护更清晰、不易出错。
常见错误是把当前距离塞进队列，结果更新 dist[] 时机混乱，导致重复入队或跳过更短路径。
- 初始化
dist[i] = -1（未访问），dist[start] = 0 - 每次从队列取出
u，遍历所有v满足graph[u][v] == 1（有边）且dist[v] == -1 - 设
dist[v] = dist[u] + 1，再 pushv
邻接矩阵 BFS 的时间复杂度真是 O(V²) 吗？
是的，而且这个开销躲不掉：每次处理一个顶点 u，都得扫描整行 graph[u][0..V-1] 找邻居。哪怕图非常稀疏（比如只有 V−1 条边），也要看 V 个位置。
对比邻接表：平均只需遍历实际出边数，稀疏图下接近 O(V+E)。所以别在十万级顶点上硬扛邻接矩阵 BFS——不是写不对，是跑不动。
立即学习“C++免费学习笔记（深入）”；
- V ≤ 1000 是邻接矩阵 BFS 的安全线
- 若图动态变化或需多次查询最短路，考虑预处理 Floyd（仅适用于 V ≤ 500）
- 编译时确定大小？用
std::array<std::array<int, N>, N>比vector<vector<int>>快 10%~20%
怎么从 BFS 结果还原最短路径（不只是长度）？
靠 dist[] 只能得到长度；要路径，必须记录前驱。加一个 prev[] 数组，初始化为 −1，每次更新 dist[v] 时设 prev[v] = u。
终点 end 的路径就是 end → prev[end] → prev[prev[end]] → ... → start，用栈或逆序 vector 构建即可。
- 别在 BFS 过程中拼字符串——字符串拷贝开销大，且无法回溯分支
- 如果只要一条路径，
prev[]足够；若需所有最短路径，得改用 DP 或 DFS 配合dist[]剪枝 - 注意：
prev[start]应保持为 −1，避免还原时多走一步
为什么 BFS 找到的第一个终点就是最短路径？
因为队列是按“距离分层”推进的：所有距离为 0 的点先入队，然后是距离为 1 的，再是距离为 2 的……所以第一次碰到 end 时，dist[end] 必然最小。
这个性质依赖两个前提：所有边权为 1（邻接矩阵隐含此假设），且队列严格遵循 FIFO。一旦混入优先队列或手动调整顺序，就变成 Dijkstra 了。
- 邻接矩阵本身不存边权？那就默认
graph[u][v] != 0表示权为 1；若需非 1 权重，BFS 不适用，必须换算法 - 无向图记得设
graph[u][v] = graph[v][u] = 1，漏设会导致单向不可达 - 起点等于终点？
dist[start]初始化为 0，BFS 循环前就该检查并返回
prev[]，后面只能重跑或加调试输出。而邻接矩阵的 O(V²) 特性，常被初学者在 V=5000 时才发现超时，不是代码错，是选型错。 
