当前位置：

首页 > 编程开发 > C++实现BFS算法详解

C++实现BFS算法详解

作者：SunnyJourney 时间：2026-01-19 浏览：0

图的广度优先搜索从起始顶点开始逐层遍历，使用队列和访问标记数组避免重复访问；C++中常用邻接表vector<vector<int>>结合queue实现，示例构建5个顶点的图并从0开始BFS，输出01234；适用于最短路径、连通分量等场景，稀疏图推荐邻接表，可扩展parent数组记录路径。

图的广度优先搜索从起始顶点开始逐层遍历，使用队列和访问标记数组避免重复访问；C++中常用邻接表vector>结合queue实现，示例构建5个顶点的图并从0开始BFS，输出0 1 2 3 4；适用于最短路径、连通分量等场景，稀疏图推荐邻接表，可扩展parent数组记录路径。

c++如何实现图的广度优先搜索(BFS)_c++ BFS算法实现与讲解

图的广度优先搜索（BFS）是一种用于遍历或搜索图的算法，它从起始顶点开始，逐层访问其邻接节点，使用队列保证访问顺序。在C++中，可以通过邻接表或邻接矩阵结合标准库queue来高效实现。

图的表示方式：邻接表

通常使用vector>表示邻接表，每个索引对应一个顶点，存储与其相连的顶点列表。

示例：

假设有5个顶点，边为 (0,1), (0,2), (1,3), (1,4)，邻接表构造如下：

vector> graph(5);
graph[0] = {1, 2};
graph[1] = {3, 4};
// 其他默认为空

BFS核心逻辑与实现步骤

BFS的关键是使用队列和访问标记数组，避免重复访问节点。

步骤说明：

创建布尔数组visited记录每个顶点是否已访问
创建队列，将起始顶点入队并标记为已访问
当队列非空时，取出队首顶点并访问
将其所有未访问的邻接顶点入队并标记
循环直到队列为空

C++实现代码：

#include 
#include 
#include 
using namespace std;

void bfs(const vector>& graph, int start) {
    int n = graph.size();
    vector visited(n, false);
    queue q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";  // 访问当前节点

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

完整可运行示例

以下是一个完整的程序，构建图并执行BFS：

int main() {
    vector> graph(5);
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0};
    graph[3] = {1};
    graph[4] = {1};

    cout << "BFS traversal: ";
    bfs(graph, 0);
    return 0;
}

输出：
0 1 2 3 4

注意事项与优化建议

BFS适用于无权图的最短路径问题，也可扩展用于层级遍历、连通分量判断等场景。

确保图的顶点编号从0开始连续，否则需用map管理visited状态
若需记录路径，可额外维护parent数组，在入队时记录前驱节点
对于稀疏图，邻接表比邻接矩阵更节省空间
注意处理孤立节点或非连通图的情况，可能需要多次调用BFS

基本上就这些。BFS结构清晰，配合STL容器写起来简洁高效。

本文内容来源于互联网，如有侵权请联系删除。

作者最新文章

图几 2026-09-16 17:43

SQL中ROUND函数对0.5的处理机制及强制四舍五入方法 2026-09-15 14:19

JS金额计算怎么避免四舍五入误差 2026-09-14 17:32

韩国8月携号转网数据：Galaxy Z8系列iPhone用户转化率约为Z7系列2倍 2026-09-08 17:02

AE基础教程：如何创建合成并制作关键帧动画 2026-09-04 09:27

编程开发 C++

上一篇：长春市民卡改支付密码教程

下一篇： Photoshop快捷键修改在哪里？PS2020快捷键设置方法

相关文章更多

C++动态数组初始化怎么写？常用语句与代码示例

内存管理 C++ 动态数组

09.21

C++类构造与析构函数详解

C++

08.17

C++中std::upper

C++

08.16

C++常对象与成员解析

C++

08.15

using namespace 使用中遇到的问题怎么解决

08.07

c语言函数递归实操经验总结：这些技巧很实用

08.07

c语言函数递归怎么选？常见方案对比分析

08.07

Objective-C 内存管理入门：从 alloc 到 dealloc 的生命周期详解

08.07

如何正确使用 dealloc 以避免 iOS 应用中的内存泄漏

08.07

深入理解 Objective-C 中的 dealloc 方法：内存管理核心机制

08.07

热门文章更多

Yandex中文入口及登录使用全攻略 51漫画高清入口及最新章节更新 B站免费入口永久有效网址推荐 58动漫网入口及永久访问方法蓝海书屋免费小说全本阅读推荐入口 B站免费入口网站高效连接方法高德地图开启海拔显示方法 ACG动漫资源站官网入口及全集链接

精品专题更多

装机必备

正软商城装机必备专区，精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件，帮助用户快速完成新电脑软件配置。

Windows

正软商城Windows软件专区，汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件，提供软件介绍、系统要求、正版授权及购买下载服务。

macOS软件

正软商城macOS软件专区，精选适用于Mac电脑的办公、设计、影音、效率、开发和系统工具，提供软件功能介绍、macOS兼容版本、正版授权及购买下载服务。

IOS软件

正软商城iOS软件专区，精选适用于iPhone和iPad的办公、学习、影音、设计、效率及AI应用，提供功能介绍、适用设备、系统要求和正版获取方式等信息。

正软商城AI软件专区，汇集AI写作、AI绘画、AI视频、AI办公、AI编程、AI翻译、智能客服和数据分析等人工智能工具，提供功能介绍、适用平台、收费方式及正版购买信息。

PDF教程

PDF教程适合刚接触PDF文件的用户,本文整理PDF打开、编辑、转换、合并、压缩等常见基础操作。通过这些教程可以快速了解PDF文件怎么处理,解决办公、学习和资料科整理中的常见问题。使用极轻PDF可在线完成多种PDF操作，适合新手快速上手。

Mac软件更多

灵活计算器

灵活计算器是一款笔记式算数应用，支持实时计算、动态关联和云端同步功能。记录、整理和输出之间的过渡会更自然，适合长期写作、做笔记或持续沉淀个人内容。

macOS软件 Android IOS软件装机必备

赤友清理大师

赤友清理大师是一款为 Mac 设计的智能清理优化工具，可精准扫描垃圾、大文件、重复文件等，释放磁盘空间。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

macOS软件装机必备

极度公式

极度公式是一款跨平台专业LaTeX公式识别编辑软件，支持OCR公式识别和多平台编辑。和使用说明，避免使用，享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

Windows macOS软件 Linux 装机必备

图几

图几是一款适用于 macOS 的截图、标注与美化工具，支持离线操作保障隐私。界面整理和高频系统操作被放到一起考虑，桌面或窗口内容一多时，管理起来会更省心。

macOS软件装机必备

密码键盘

密码键盘是一款兼具安全性与便捷性的高效密码管理器。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows macOS软件 Android IOS软件装机必备

思源笔记

思源笔记是一款本地笔记软件，提供所见即所得的编辑方式，为长文写作带来顺滑的体验。记录、整理和输出之间的过渡会更自然，适合长期写作、做笔记或持续沉淀个人内容。

Windows macOS软件 Android IOS软件装机必备

Office 365 简体中文

一款文字处理软件，一种订阅式的跨平台办公软件，基于云平台提供多种服务，通过将 Excel 和 Outlook 等应用与 OneDrive 和 Microsoft Teams 等强大的云服务相结合，Office 365 可让任何人使用任何设备随时随地创建和共享内容。

WALTR PRO

WALTR是一款电脑至iOS文件传输转换工具，操作简单，快速实现文件识别与传送。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

Windows macOS软件

CodeExpander

CodeExpander 是一款快捷短语输入增强工具，通过键入缩写自动展开为自定义文段，提升工作效率。任务管理和过程控制会更完整，持续下载、批量同步或需要稳定传输流程的场景会更适合它。

Windows macOS软件

Mountain Duck

Mountain Duck 是一款能将多个网盘挂载到本地的工具，像本地磁盘一样使用网盘。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。

Windows macOS软件

Menuist

Menuist 是一款面向 macOS 的 Finder 右键菜单增强工具，主要用来补充新建文件、快捷导航等常用操作，让日常文件管理和访问路径时更高效、更顺手。

macOS软件

Mole

Mole 是一款专为 Mac 设计的深度清理优化工具，涵盖缓存清理、应用管理及实时状态监控等功能。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。

macOS软件

WINDOWS 更多

Windows 10

Windows 10 是一款微软推出的经典操作系统，拥有硬件兼容性与多任务处理能力。它更偏向把系统状态查看和常用调节动作放在一起，适合需要持续观察和微调设备状态的场景。

Windows 10 Windows 操作系统装机必备

极度公式

Windows macOS软件 Linux 装机必备

密码键盘

密码键盘是一款兼具安全性与便捷性的高效密码管理器。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows macOS软件 Android IOS软件装机必备

思源笔记

Windows macOS软件 Android IOS软件装机必备

傲梅轻松备份

傲梅轻松备份是一款专业易用的数据备份软件，为重要数据提供安全保障。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows 装机必备

Office 365 简体中文

Wise Folder Hider Pro

Wise Folder Hider Pro 是一款专业级文件和文件夹隐藏加密软件，为私密数据添加多重保护。高频操作更强调就近处理，浏览、整理和跨目录移动文件时，来回切换和重复点击都会少很多。

Windows

WALTR PRO

Windows macOS软件

CodeExpander

Windows macOS软件

PinStack

PinStack是一款轻量级的Windows平台剪贴板管理工具，优化您的剪贴板使用体验。它更偏向把系统状态查看和常用调节动作放在一起，适合需要持续观察和微调设备状态的场景。

Windows

Mountain Duck

Windows macOS软件

Seer

Seer是一款在Win平台下的空格键功能增强效率工具，只需轻敲空格键，就能预览几乎任何格式的文件。它更适合把零散的小功能集中起来使用，处理高频琐碎任务时会更省事。

Windows