c++如何实现广度优先搜索_c++ BFS算法实现【源码】

标准BFS遍历用std::queue实现：取队首节点，访问其未访问邻接点并入队；邻接表用std::vector节省空间，visited数组防重复入队。

用 std::queue 实现标准 BFS 遍历

核心就是维护一个先进先出的队列，每次取出队首节点，访问它所有未访问过的邻接点并入队。C++ 标准库的 std::queue 是最直接的选择，不需要手写队列结构。

关键点：

• 用 std::vector<:vector>> 存邻接表，比邻接矩阵更省空间（尤其稀疏图）
• 用 std::vector 记录访问状态，下标即节点编号，避免重复入队
• 入队前必须检查是否已访问，否则可能无限循环或结果错乱

示例片段（无向图）：

std::vector> graph = {{1,2}, {0,3}, {0,3}, {1,2}};
std::vector visited(graph.size(), false);
std::queue q;
q.push(0);
visited[0] = true;

while (!q.empty()) {
    int u = q.front(); q.pop();
    std::cout << u << " ";
    for (int v : graph[u]) {
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

处理带权图或需要路径还原的 BFS

BFS 本身不适用于带权图的最短路径（除非所有边权相等），但若图中边权均为 1，BFS 天然给出单源最短距离；若还需知道怎么走到的，就得额外记录父节点。

立即学习“C++免费学习笔记（深入）”；

梅子Ai论文

无限免费生成千字论文大纲-在线快速生成论文初稿-查重率10%左右

下载

常见做法：

• 加一个 std::vector parent，初始化为 -1，每次从 u 扩展到 v 时设 parent[v] = u
• 距离数组 dist 可用 std::vector，初始填 -1 或 INT_MAX，dist[source] = 0，之后 dist[v] = dist[u] + 1
• 路径还原时从目标节点不断跳 parent，直到 -1，再逆序输出

遇到 “超时” 或 “内存爆炸” 怎么办

不是算法逻辑错，而是数据结构或边界没控住。典型诱因：

• 图节点数极大（比如 1e5），但用了二维邻接矩阵（vector>(n, vector(n))），直接 O(n²) 内存炸掉 → 改用邻接表
• 没判重就 push 进队列，导致同一节点反复入队（比如无向图中 u→v 后又 v→u），队列迅速膨胀 → 必须在 push 前查 visited[v]
• 输入格式含自环或重边，虽不影响正确性，但会徒增遍历次数 → 可在建图时去重，或依赖 visited 自然过滤

和 DFS 混用时容易踩的坑

BFS 和 DFS 共享同一张图、同一套 visited 数组时，顺序和结果会互相干扰。实际项目中常见错误：

• 先跑一遍 BFS 把 visited 全设为 true，接着调 DFS 却发现“什么都没走” → 解决：每次搜索前重置 visited，或用局部变量
• 误以为 BFS 能像 DFS 那样方便回溯（比如找所有路径），但 BFS 天然不保存路径分支 → 真要枚举所有路径，得用 DFS 或改造 BFS 存完整路径（空间代价高）
• 多源 BFS（如多个起点同时开始）忘记把所有起点一次性 push 到队列并标记 → 结果只从第一个起点展开

真正难的不是写对一次 BFS，而是清楚它在哪种图结构、哪种问题约束下依然可靠——比如节点编号不连续、图用字符串 ID 而非整数、或者需要实时中断搜索。这些场景下，队列元素类型和访问标记方式都得跟着变。