当前位置: 首页 > news >正文

深入解析队列与广度优先搜索(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的核心思想是使用队列来存储待访问的节点。具体步骤如下:

  1. 将起始节点放入队列。

  2. 从队列中取出一个节点,访问它。

  3. 将该节点的所有未访问过的相邻节点放入队列。

  4. 重复步骤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. 广度优先搜索&#xff08;BFS&#xff09;的基本概念 3. 队列在BFS中的作用 4. BFS的实现细节 5. C实现BFS 6. BFS的应用场景 7. 复杂度分析 8. 总结 1. 队列的基本概念 队列&#xff08;Queue&#xff09;是一种先进先出&#xff08;FIFO, …...

Swap to Gather-----

C - 烟销日出不见人 问题陈述 给定一个长度为 NN 的字符串 SS&#xff0c;由 0 和 1 组成。保证 SS 至少包含一个 1。 您可以执行以下操作任意次数&#xff08;可能为零&#xff09;&#xff1a; 选择一个整数 ii (1≤i≤N−11≤i≤N−1)&#xff0c;并交换 SS 的第 ii 个和…...

使用DeepSeek+本地知识库,尝试从0到1搭建高度定制化工作流(自动化篇)

7.5. 配图生成 目的&#xff1a;由于小红书发布文章要求图文格式&#xff0c;因此在生成文案的基础上&#xff0c;我们还需要生成图文搭配文案进行发布。 原实现思路&#xff1a; 起初我打算使用deepseek的文生图模型Janus进行本地部署生成&#xff0c;参考博客&#xff1a;De…...

Python 函数式编程全攻略:从理论到实战的深度解析

本文深入剖析 Python 函数式编程&#xff0c;详细讲解其概念、核心特性&#xff08;迭代器、生成器等&#xff09;、内置函数及相关模块&#xff08;itertools、functools &#xff09;&#xff0c;结合丰富示例与直观图表&#xff0c;助力读者全面掌握函数式编程技巧&#xff…...

Ollama 在 LangChain 中的使用

文章目录 一、langChain 介绍二、环境安装1.依赖库安装2.下载模型 三、基本使用示例1.使用 ChatPromptTemplate 进行对话2.流式输出3.工具调用4.多模态模型调用 四、进阶使用1.使用 ConversationChain 进行对话2.自定义提示模板3.构建一个简单的 RAG 问答系统 五、遇到问题与解…...

使用apt-rdepends制作软件离线deb安装包

使用apt-rdepends制作软件离线deb安装包 除基础软件外&#xff0c;还要获取软件依赖包。 依赖包工具安装 apt-get install apt-rdependsapt-rdepends工具使用 使用apt-rdepends工具&#xff0c;递归方式分析软件依赖&#xff0c;下载软件包本体&#xff0c;和依赖包。制作时…...

根据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# 如果没有传参&#xff0c;则提示用户输入 Pod 名称echo -e "${YELLOW}Please enter the Pod name:${…...

SQL sever数据导入导出实验

1.创建数据库TCP-H &#xff08;1&#xff09;右键“数据库”&#xff0c;点击“新建数据库”即可 &#xff08;2&#xff09;用sql语言创建&#xff0c;此处以创建数据库DB_test为例&#xff0c;代码如下&#xff1a; use master;go--检查在当前服务器系统中的所有数据里面…...

python环境的yolov11.rknn物体检测

1.首先是我手里生成的一个yolo11的.rknn模型&#xff1a; 2.比对一下yolov5的模型&#xff1a; 2.1 yolov5模型的后期处理&#xff1a; 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&#xff1a;串口通信&#xff0c;同步&#xff0c;半双工&#xff0c;双线&#xff08;数据线SDA时钟线SCL&#xff09;&#xff0c;最大距离1米到几米 SPI&#xff08;串行外设接口&#xff09;&#xff1a;串口通信&#xff0c;同步&#xff0c;全双工&#xff0c;四线&…...

如何监控和优化 MySQL 中的慢 SQL

如何监控和优化 MySQL 中的慢 SQL 前言一、什么是慢 SQL&#xff1f;二、如何监控慢 SQL&#xff1f;1. 启用慢查询日志启用方法&#xff1a;日志内容&#xff1a; 2. 使用 mysqldumpslow 分析日志 三、如何分析慢 SQL&#xff1f;1. 使用 EXPLAIN 分析执行计划使用方法&#x…...

13-二叉树最小深度-深度优先(DFS)

一、定义 什么是二叉树的最小深度&#xff1f; 二叉树的最小深度是指从根节点到最近的叶子节点的最短路径上的节点数。叶子节点是指没有子节点的节点。 举个例子&#xff1a; 1/ \2 3/ 4 这棵树的最小深度是 2&#xff0c;因为从根节点 1 到叶子节点 3 的路径最短&#x…...

51单片机入门_10_数码管动态显示(数字的使用;简单动态显示;指定值的数码管动态显示)

接上篇的数码管静态显示&#xff0c;以下是接上篇介绍到的动态显示的原理。 动态显示的特点是将所有位数码管的段选线并联在一起&#xff0c;由位选线控制是哪一位数码管有效。选亮数码管采用动态扫描显示。所谓动态扫描显示即轮流向各位数码管送出字形码和相应的位选&#xff…...

代码补全『三重奏』:EverEdit如何用上下文识别+语法感知+智能片段重构你的编码效率!

1 代码自动完成 1.1 应用场景 在编辑文档时&#xff0c;为了提高编辑效率&#xff0c;编辑器一般都会带有自动完成功能&#xff0c;比如&#xff1a;输入括号时自动补全另一半&#xff0c;输入文字时&#xff0c;自动补全剩下的部分。 1.2 使用方法 1.2.1 自动缩进 单击主菜…...

电脑系统损坏,备份文件

一、工具准备 1.U盘&#xff1a;8G以上就够用&#xff0c;注意会格式化U盘&#xff0c;提前备份U盘内容 2.电脑&#xff1a;下载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注意力算子&#xff0c;通过对最大编码率降低&#xff08; M C R 2 MCR^{2} MCR2&#xff09;目标的变分形式进行展开优化得到&…...

Django 5实用指南(二)项目结构与管理

2.1 Django5项目结构概述 当你创建一个新的 Django 项目时&#xff0c;Django 会自动生成一个默认的项目结构。这个结构是根据 Django 的最佳实践来设计的&#xff0c;以便开发者能够清晰地管理和维护项目中的各种组件。理解并管理好这些文件和目录结构是 Django 开发的基础。…...

JAVA监听器(学习自用)

一、什么是监听器 servlet监听器是一种特殊的接口&#xff0c;用于监听特定的事件&#xff08;如请求创建和销毁、会话创建和销毁、上下文的初始化和销毁&#xff09;。 当Web应用程序中反生特定事件时&#xff0c;Servlet容器就会自动调用监听器中相应的方法来处理这些事件。…...

Ubuntu下mysql主从复制搭建

本文介绍mysql 8.4主从集群的搭建&#xff0c;从单个机器安装到集群的配置&#xff0c;整体走了一遍&#xff0c;希望对大家有帮助。mysql 8.4和之前的版本命令上有些变化&#xff0c;大家用来参考。 0、环境 ubuntu&#xff1a; 22.04mysql&#xff1a;8.4 1、安装mysql 1…...

VirtualBox 中使用 桥接网卡 并设置 MAC 地址

在 VirtualBox 中使用 桥接网卡 并设置 MAC 地址&#xff0c;可以按照以下步骤操作&#xff1a; 步骤 1&#xff1a;设置桥接网卡 打开 VirtualBox&#xff0c;选择你的虚拟机&#xff0c;点击 “设置” (Settings)。进入 “网络” (Network) 选项卡。在 “适配器 1” (Adapt…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...