深入解析队列与广度优先搜索(BFS)的算法思想:原理、实现与应用
目录
1. 队列的基本概念
2. 广度优先搜索(BFS)的基本概念
3. 队列在BFS中的作用
4. BFS的实现细节
5. C++实现BFS
6. BFS的应用场景
7. 复杂度分析
8. 总结
1. 队列的基本概念
队列(Queue)是一种先进先出(FIFO, First In First Out)的线性数据结构。它有两个主要操作:
-
入队(Enqueue):将元素添加到队列的末尾。
-
出队(Dequeue):移除队列的第一个元素。
在C++中,队列可以通过STL中的std::queue来实现:
#include <queue>std::queue<int> q;
q.push(1); // 入队
q.pop(); // 出队
int front = q.front(); // 获取队首元素
2. 广度优先搜索(BFS)的基本概念
广度优先搜索(BFS, Breadth-First Search)是一种用于遍历或搜索树或图的算法。BFS从根节点(或任意节点)开始,逐层遍历所有相邻节点,直到找到目标节点或遍历完所有节点。
BFS的核心思想是使用队列来存储待访问的节点。具体步骤如下:
-
将起始节点放入队列。
-
从队列中取出一个节点,访问它。
-
将该节点的所有未访问过的相邻节点放入队列。
-
重复步骤2和3,直到队列为空。
3. 队列在BFS中的作用
队列在BFS中起到了关键作用,它保证了节点按照层次顺序被访问。具体来说:
-
层次遍历:队列确保每一层的节点都在下一层节点之前被访问。
-
避免重复访问:通过标记已访问的节点,可以避免重复访问和无限循环。
4. BFS的实现细节
在实现BFS时,需要注意以下几个关键点:
-
访问标记:通常使用一个数组或哈希表来记录哪些节点已经被访问过。
-
队列操作:每次从队列中取出一个节点,访问它,并将其未访问的相邻节点加入队列。
-
终止条件:当队列为空时,BFS结束。
5. C++实现BFS
下面是一个使用队列实现BFS的C++代码示例,假设我们有一个无向图,用邻接表表示:
#include <iostream>
#include <queue>
#include <vector>void BFS(int start, const std::vector<std::vector<int>>& graph) {std::vector<bool> visited(graph.size(), false);std::queue<int> q;q.push(start);visited[start] = true;while (!q.empty()) {int node = q.front();q.pop();std::cout << "Visited node: " << node << std::endl;for (int neighbor : graph[node]) {if (!visited[neighbor]) {q.push(neighbor);visited[neighbor] = true;}}}
}int main() {// 示例图的邻接表表示std::vector<std::vector<int>> graph = {{1, 2}, // 节点0的邻居{0, 3, 4}, // 节点1的邻居{0, 5}, // 节点2的邻居{1}, // 节点3的邻居{1}, // 节点4的邻居{2} // 节点5的邻居};BFS(0, graph); // 从节点0开始BFSreturn 0;
}
6. BFS的应用场景
BFS广泛应用于各种场景,包括但不限于:
-
最短路径问题:在无权图中,BFS可以找到从起点到目标节点的最短路径。
-
连通性检测:BFS可以用于检测图中的连通分量。
-
状态空间搜索:在解决某些问题时,BFS可以用于搜索状态空间,如八数码问题、迷宫问题等。
7. 复杂度分析
-
时间复杂度:BFS的时间复杂度为O(V + E),其中V是顶点数,E是边数。每个节点和每条边都会被访问一次。
-
空间复杂度:BFS的空间复杂度主要取决于队列的大小,最坏情况下为O(V)。
8. 总结
“队列+宽搜”是一种经典的算法思想,通过队列的先进先出特性,BFS能够有效地遍历图或树结构,并解决许多实际问题。理解队列在BFS中的作用以及如何正确实现BFS是掌握这一算法思想的关键。通过C++的实现,我们可以清晰地看到队列如何帮助BFS逐层遍历节点,并确保每个节点只被访问一次。
相关文章:
深入解析队列与广度优先搜索(BFS)的算法思想:原理、实现与应用
目录 1. 队列的基本概念 2. 广度优先搜索(BFS)的基本概念 3. 队列在BFS中的作用 4. BFS的实现细节 5. C实现BFS 6. BFS的应用场景 7. 复杂度分析 8. 总结 1. 队列的基本概念 队列(Queue)是一种先进先出(FIFO, …...
Swap to Gather-----
C - 烟销日出不见人 问题陈述 给定一个长度为 NN 的字符串 SS,由 0 和 1 组成。保证 SS 至少包含一个 1。 您可以执行以下操作任意次数(可能为零): 选择一个整数 ii (1≤i≤N−11≤i≤N−1),并交换 SS 的第 ii 个和…...
使用DeepSeek+本地知识库,尝试从0到1搭建高度定制化工作流(自动化篇)
7.5. 配图生成 目的:由于小红书发布文章要求图文格式,因此在生成文案的基础上,我们还需要生成图文搭配文案进行发布。 原实现思路: 起初我打算使用deepseek的文生图模型Janus进行本地部署生成,参考博客:De…...
Python 函数式编程全攻略:从理论到实战的深度解析
本文深入剖析 Python 函数式编程,详细讲解其概念、核心特性(迭代器、生成器等)、内置函数及相关模块(itertools、functools ),结合丰富示例与直观图表,助力读者全面掌握函数式编程技巧ÿ…...
Ollama 在 LangChain 中的使用
文章目录 一、langChain 介绍二、环境安装1.依赖库安装2.下载模型 三、基本使用示例1.使用 ChatPromptTemplate 进行对话2.流式输出3.工具调用4.多模态模型调用 四、进阶使用1.使用 ConversationChain 进行对话2.自定义提示模板3.构建一个简单的 RAG 问答系统 五、遇到问题与解…...
使用apt-rdepends制作软件离线deb安装包
使用apt-rdepends制作软件离线deb安装包 除基础软件外,还要获取软件依赖包。 依赖包工具安装 apt-get install apt-rdependsapt-rdepends工具使用 使用apt-rdepends工具,递归方式分析软件依赖,下载软件包本体,和依赖包。制作时…...
根据POD名称生成 三部曲:get、describe、log、exec
#!/bin/bash# 定义颜色变量 RED\033[0;31m GREEN\033[0;32m YELLOW\033[0;33m NC\033[0m # No Color# 检查是否传入 Pod 名称作为参数 if [ -z "$1" ]; then# 如果没有传参,则提示用户输入 Pod 名称echo -e "${YELLOW}Please enter the Pod name:${…...
SQL sever数据导入导出实验
1.创建数据库TCP-H (1)右键“数据库”,点击“新建数据库”即可 (2)用sql语言创建,此处以创建数据库DB_test为例,代码如下: use master;go--检查在当前服务器系统中的所有数据里面…...
python环境的yolov11.rknn物体检测
1.首先是我手里生成的一个yolo11的.rknn模型: 2.比对一下yolov5的模型: 2.1 yolov5模型的后期处理: outputs rknn.inference(inputs[img2], data_format[nhwc])np.save(./onnx_yolov5_0.npy, outputs[0])np.save(./onnx_yolov5_1.npy, outpu…...
I2C、SPI、UART
I2C:串口通信,同步,半双工,双线(数据线SDA时钟线SCL),最大距离1米到几米 SPI(串行外设接口):串口通信,同步,全双工,四线&…...
如何监控和优化 MySQL 中的慢 SQL
如何监控和优化 MySQL 中的慢 SQL 前言一、什么是慢 SQL?二、如何监控慢 SQL?1. 启用慢查询日志启用方法:日志内容: 2. 使用 mysqldumpslow 分析日志 三、如何分析慢 SQL?1. 使用 EXPLAIN 分析执行计划使用方法&#x…...
13-二叉树最小深度-深度优先(DFS)
一、定义 什么是二叉树的最小深度? 二叉树的最小深度是指从根节点到最近的叶子节点的最短路径上的节点数。叶子节点是指没有子节点的节点。 举个例子: 1/ \2 3/ 4 这棵树的最小深度是 2,因为从根节点 1 到叶子节点 3 的路径最短&#x…...
51单片机入门_10_数码管动态显示(数字的使用;简单动态显示;指定值的数码管动态显示)
接上篇的数码管静态显示,以下是接上篇介绍到的动态显示的原理。 动态显示的特点是将所有位数码管的段选线并联在一起,由位选线控制是哪一位数码管有效。选亮数码管采用动态扫描显示。所谓动态扫描显示即轮流向各位数码管送出字形码和相应的位选ÿ…...
代码补全『三重奏』:EverEdit如何用上下文识别+语法感知+智能片段重构你的编码效率!
1 代码自动完成 1.1 应用场景 在编辑文档时,为了提高编辑效率,编辑器一般都会带有自动完成功能,比如:输入括号时自动补全另一半,输入文字时,自动补全剩下的部分。 1.2 使用方法 1.2.1 自动缩进 单击主菜…...
电脑系统损坏,备份文件
一、工具准备 1.U盘:8G以上就够用,注意会格式化U盘,提前备份U盘内容 2.电脑:下载Windows系统并进行启动盘制作 二、Windows启动盘制作 1.微软官网下载启动盘制作工具微软官网下载启动盘制作工具https://www.microsoft.com/zh-c…...
Token Statistics Transformer:线性注意力革命,重新定义Transformer效率天花板
“TOKEN STATISTICS TRANSFORMER: LINEAR-TIME ATTENTION VIA VARIATIONAL RATE REDUCTION” 由Ziyang Wu等人撰写。文章提出一种新型Transformer注意力算子,通过对最大编码率降低( M C R 2 MCR^{2} MCR2)目标的变分形式进行展开优化得到&…...
Django 5实用指南(二)项目结构与管理
2.1 Django5项目结构概述 当你创建一个新的 Django 项目时,Django 会自动生成一个默认的项目结构。这个结构是根据 Django 的最佳实践来设计的,以便开发者能够清晰地管理和维护项目中的各种组件。理解并管理好这些文件和目录结构是 Django 开发的基础。…...
JAVA监听器(学习自用)
一、什么是监听器 servlet监听器是一种特殊的接口,用于监听特定的事件(如请求创建和销毁、会话创建和销毁、上下文的初始化和销毁)。 当Web应用程序中反生特定事件时,Servlet容器就会自动调用监听器中相应的方法来处理这些事件。…...
Ubuntu下mysql主从复制搭建
本文介绍mysql 8.4主从集群的搭建,从单个机器安装到集群的配置,整体走了一遍,希望对大家有帮助。mysql 8.4和之前的版本命令上有些变化,大家用来参考。 0、环境 ubuntu: 22.04mysql:8.4 1、安装mysql 1…...
VirtualBox 中使用 桥接网卡 并设置 MAC 地址
在 VirtualBox 中使用 桥接网卡 并设置 MAC 地址,可以按照以下步骤操作: 步骤 1:设置桥接网卡 打开 VirtualBox,选择你的虚拟机,点击 “设置” (Settings)。进入 “网络” (Network) 选项卡。在 “适配器 1” (Adapt…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
