c++中如何实现图的广度优先遍历_c++图BFS遍历方法

尼克

发布时间：2025-10-07 21:31:01

216人浏览过

来源于php中文网

原创

答案：C++中BFS通过队列实现逐层遍历，使用邻接表存储图并用visited数组标记节点，从起始点入队开始，循环出队并访问其未标记的邻接点，直至队列为空，确保每个节点仅处理一次，时间复杂度为O(V+E)。

c++中如何实现图的广度优先遍历_c++图bfs遍历方法

在C++中实现图的广度优先遍历（BFS），核心是使用队列结构来逐层访问图中的节点。BFS适用于无向图或有向图，常用于寻找最短路径、连通性判断等场景。

图的存储方式：邻接表

通常用邻接表表示图，便于遍历每个节点的邻居。可以使用vector>来实现。

例如，graph[u] 存储所有与节点 u 相连的节点。

实现步骤说明

BFS的关键在于从起始节点出发，逐层扩展，避免重复访问。需要一个队列和一个标记数组。

知识画家

AI交互知识生成引擎，一句话生成知识视频、动画和应用

下载

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

创建一个布尔数组 visited，记录节点是否被访问过
使用 queue 存储待访问的节点
将起始节点入队，并标记为已访问
当队列不为空时，取出队首节点，访问其所有未访问的邻接点并入队

代码示例

以下是一个完整的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);
            }
        }
    }
}

int main() {
    int n = 5;
    vector> graph(n);

    // 构建无向图：0-1, 0-2, 1-3, 2-4
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2};

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

    return 0;
}

注意事项

BFS确保每个节点只被处理一次，时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。

记得初始化 visited 数组，防止重复访问
对于非连通图，可能需要对每个未访问节点调用 BFS
如果图是用邻接矩阵存储的，遍历邻接点的方式要改为循环检查 matrix[u][v]

基本上就这些。只要掌握队列和访问标记的配合，BFS就不难实现。

C++如何实现一个A*寻路算法？C++游戏AI与路径规划【算法实战】

c++在Unreal Engine中的应用_c++ UE4/5游戏开发基础

如何用C++实现一个有限状态机（FSM）？C++游戏AI与协议解析【设计模式】

c++如何实现一个简单的神经网络推理框架_c++ ONNX Runtime集成【AI】

c++如何使用TensorRT进行模型部署优化_c++ NVIDIA推理引擎入门【AI】

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

ai c++ ios stream int 循环

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++怎么处理跨平台编译问题_c++跨平台编译方法下一篇：c++怎么把char数组转成string_C++ char*与string类型转换方法

作者最新文章

QQ音乐网页版官方入口_QQ音乐官网在线听歌

2026-01-29 13:37

C++ string流怎么清空 C++ stringstream clear与str("")区别【流】

2026-01-29 13:46

C++ char和char[]区别 C++字符串常量与数组内存分布【基础】

2026-01-29 13:49

Sublime怎么配置C语言编译系统 Sublime运行C程序详细教程【指南】

2026-01-29 13:58

百度智慧农场智慧平台入口百度智慧农场官网首页登录

2026-01-29 13:59

C++ 怎么实现栈 C++ stack容器适配器使用教程【容器】

2026-01-29 14:03

Composer怎么安装Dotenv库环境变量加载配置指南【教程】

2026-01-29 14:13

C++ shared_ptr线程安全吗 C++ 引用计数与对象访问安全性【多线程】

2026-01-29 14:13

C++中如何高效地拼接字符串？(使用std::stringstream或reserve预留空间)

2026-01-29 14:20

c++的错误码(error code)和异常(exception)该如何抉择？ (Herb Sutter的观点)

2026-01-29 14:23

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发 AI 聊天问答

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发 AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI 编程开发 Agent智能体

腾讯元宝

腾讯混元平台推出的AI助手

文档处理 AI 聊天问答

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发 AI 文本写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发 AI 文本写作

智谱清言 - 免费全能的AI助手

AI 编程开发 Agent智能体

相关专题

string转int

在编程中，我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算，或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

463

2023.08.02

int占多少字节

int占4个字节，意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值，在某些情况下也可能是2个字节或8个字节，int是一种常用的数据类型，用于表示整数，需要根据具体情况选择合适的数据类型，以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

544

2024.08.29