C++实现广度优先搜索BFS _ 队列实现最短路径查找【详解】-C++-PHP中文网

std::queue 本身不存距离，需用额外容器（如 vector 或 unordered_map）记录各节点最短距离；核心在于状态定义、入队时机与重复访问判断，而非队列语法。

c++实现广度优先搜索bfs _ 队列实现最短路径查找【详解】

用 std::queue 实现 BFS 查最短路径，核心不是“队列怎么用”，而是“状态怎么定义、何时入队、何时跳过”——多数人卡在重复访问和距离更新上，不是语法问题。

为什么 `std::queue` 本身不存距离？得靠额外数组或哈希表

BFS 的“最短”依赖于层序扩展，但 std::queue 只负责 FIFO 存节点（比如 int 编号或 std::pair<int></int> 坐标），它不记录该节点到起点的距离。必须配合一个独立容器（如 std::vector<int></int> 或 std::unordered_map<key int></key>）来存每个节点的最短距离（或是否已访问）。

图中节点编号为 0 到 n-1？优先用 std::vector<int> dist(n, -1)</int>，初始化为 -1 表示未访问
节点是坐标 (r, c) 或字符串 ID？用 std::unordered_map<:pair>, int, PairHash></:pair> 或 std::map，但注意 std::pair 默认不可哈希，需自定义 Hash 或改用 std::tuple/std::string
别在入队时“猜”距离：错误写法 q.push({next, dist[cur] + 1}) 看似省事，但若 next 已被更短路径访问过，这次入队就冗余且破坏 BFS 层序性

`dist[node] == -1` 是关键判断条件，不是 `!visited[node]`

很多初学者用单独的 visited 数组，再加一层 if (!visited[node]) { visited[node] = true; ... }。这看似清晰，实则多了一次内存访问，且容易和 dist 不同步。直接用 dist[node] == -1 既表示未访问，又天然支持“首次到达即最短”的语义。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

入队前检查：if (dist[next] == -1) { dist[next] = dist[cur] + 1; q.push(next); }
如果图有权重（哪怕全是正权），BFS 失效，必须换 Dijkstra —— 这里 dist[node] == -1 的逻辑依然成立，但算法本身不适用
网格中越界检查必须在 dist 判断之前，否则可能访问 dist[-1] 导致崩溃

邻接表遍历时，别漏掉反向边（无向图）或建错有向边

广搜跑不通，80% 是图结构建错了。BFS 本身很稳定，问题常出在 graph[u] 拿不到 v。

无向图：添加边时必须双向，graph[u].push_back(v); graph[v].push_back(u);
有向图：只加 graph[u].push_back(v)，别手抖写成 graph[v].push_back(u)
网格类题目（如上下左右移动）：四个方向偏移量写成 {-1,0}, {1,0}, {0,-1}, {0,1}，别漏掉负号或写反顺序
用 std::vector<:vector>> graph</:vector> 存邻接表？确认 graph 大小初始化正确，比如 graph.resize(n) 后再对每个 i 执行 graph[i].reserve(4) 避免频繁扩容