c++怎么实现广度优先搜索bfs_c++ 队列实现与最短路径寻找【教程】

std::queue 是 c++ 中实现 bfs 的核心容器，需配合 visited 标记、邻接表存储、距离数组 dist 和边界检查；起点入队前标记 visited，每次取队首后立即 pop，遍历未访问邻居并更新 dist，避免重复入队与越界访问。

用 std::queue 实现 BFS 的核心结构

广度优先搜索在 C++ 中最自然的实现方式就是依赖 std::queue，它保证先进先出，正好匹配 BFS 逐层扩展的逻辑。关键不是“怎么写循环”，而是“存什么、怎么标记、何时停止”。节点通常存索引或指针，但必须配合访问标记（如 vector<bool> visited</bool>），否则会重复入队甚至死循环。

• 图的表示建议用 vector<vector>></vector>（邻接表），比邻接矩阵更省空间且遍历快
• 起点入队前必须设 visited[start] = true，否则可能被重复加入
• 每次从队首取节点后立刻 pop，再遍历其所有未访问邻居——顺序不能颠倒

记录最短路径长度：用 vector<int></int> 存距离而非层数计数器

很多人用一个全局 level 变量来统计层数，但这在非完全二叉树或稀疏图中极易出错。正确做法是为每个节点单独维护到达它的最短距离，初始化为 -1（未访问）或 INT_MAX，起点设为 0。每次扩展邻居时更新：dist[neighbor] = dist[current] + 1。

DoMore.ai

DoMore.ai 是一个个性化的 AI 工具目录

下载

• 这样不仅能拿到终点距离，还能回溯路径（需额外存 parent 数组）
• 如果只关心是否存在路径，可提前在 if (neighbor == target) 时 return dist[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<int>>& 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; // 不可达
}