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

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

发布时间 - 2026-01-26 00:00:00 点击率：次

标准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++免费学习笔记（深入）”；

常见做法：

加一个 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 而非整数、或者需要实时中断搜索。这些场景下，队列元素类型和访问标记方式都得跟着变。

# c++ # 标准库 # 局部变量 # 字符串 # 循环 # 数据结构 # 算法 # 遍历 # 哪种 # 最短 # 图中 # 第一个 # 多个 # 不需要 # 走到 # 设为 # 均为

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：Go语言初级项目如何部署_Golang项目上线实战

下一篇：VSCode怎么删除所有断点_VSCode一键清除所有调试断

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher