std::queue 是 C++ 中实现 BFS 的核心容器，需配合 visited 标记、邻接表存储、距离数组 dist 和边界检查；起点入队前标记 visited，每次取队首后立即 pop，遍历未访问邻居并更新 dist，避免重复入队与越界访问。
用 std::queue 实现 BFS 的核心结构
广度优先搜索在 C++ 中最自然的实现方式就是依赖 std::queue，它保证先进先出，正好匹配 BFS 逐层扩展的逻辑。关键不是“怎么写循环”，而是“存什么、怎么标记、何时停止”。节点通常存索引或指针，但必须配合访问标记（如 vector），否则会重复入队甚至死循环。
- 图的表示建议用
vector（邻接表），比邻接矩阵更省空间且遍历快> - 起点入队前必须设
visited[start] = true，否则可能被重复加入 - 每次从队首取节点后立刻 pop，再遍历其所有未访问邻居——顺序不能颠倒
记录最短路径长度：用 vector 存距离而非层数计数器
很多人用一个全局 level 变量来统计层数，但这在非完全二叉树或稀疏图中极易出错。正确做法是为每个节点单独维护到达它的最短距离，初始化为 -1（未访问）或 INT_MAX，起点设为 0。每次扩展邻居时更新：dist[neighbor] = dist[current] + 1。
- 这样不仅能拿到终点距离，还能回溯路径（需额外存
parent数组） - 如果只关心是否存在路径，可提前在
if (neighbor == target)时 returndist[current] + 1 - 注意：无向图中边权为 1 才适用此方法；带权图必须换 Dijkstra
避免常见错误：重复入队、越界访问、空图处理
实际写的时候，这几个点最容易导致运行时崩溃或逻辑错误：
-
queue为空时还调用front()或pop()→ 必须每次while (!q.empty())开头检查 - 邻接表索引越界：比如节点编号从 1 开始，但
vector下标从 0 开始 → 访问graph[u]前确认u - 没处理孤立节点：起点本身不可达其他点，
visited和dist初始值要统一设为 -1 或无效值 - 多起点？把多个起点同时 push 进队列，并设对应
dist为 0 —— 这是多源 BFS 的标准写法
#include <queue>
#include <vector>
#include <climits>
using namespace std;
int bfs_shortest_path(const vector<vector>>& graph, int start, int target) {
if (start == target) return 0;
int n = graph.size();
vector<int> dist(n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
if (v == target) return dist[v];
q.push(v);
}
}
}
return -1; // 不可达
}
</int></int></vector></climits></vector></queue>
BFS 看似简单，但真正稳定跑通的关键在于：每一步入队前检查是否已访问，每一步出队后立即更新邻居状态，距离数组和访问标记必须同步维护。图结构不规范、边界没兜底，函数就可能静默返回错误结果。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
