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

广度优先搜索（BFS）算法详解——以走迷宫问题为例

news 来源：原创 2025/5/9 22:54:41

引言：当算法遇见迷宫

想象你置身于一个复杂的迷宫，如何在最短时间内找到出口？这个问题不仅存在于童话故事中，更是计算机科学中经典的路径搜索问题。本文将带你通过走迷宫问题，深入理解广度优先搜索（BFS）这一强大的算法工具。

一、BFS算法原理剖析

1.1 BFS & DFS

在这里插入图片描述

1.2 算法核心思想

广度优先搜索采用"层层推进"的策略：

使用队列数据结构管理待探索节点
在每一个点处，所有可能到达的不重复的下一个节点都会被添加到队列中

简单来说，在遇到岔路时，会进行分身,两边同时进行探索。

1.3 算法实现框架

void bfs(起点) {初始化队列标记起点已访问while (队列不为空) {取出队首节点if (到达终点) {返回结果}for (所有相邻节点) {if (节点合法且未访问) {标记已访问加入队列}}}
}

1.4 算法特性分析

时间复杂度： $O (V + E)$ （ $V$ 为顶点数， $E$ 为边数）
空间复杂度： $O (V)$
优势：保证找到最短路径
局限：空间开销较大

二、走迷宫问题建模

2.1 问题描述

给定一个 $n * m$ 的迷宫：

$0$ 表示可通行的路径
$1$ 表示障碍物
从左上角 $(1, 1)$ 出发，寻找到达右下角 $(n, m)$ 的最短路径

2.2 问题转化

将迷宫建模为图：

节点：每个可通行的格子
边：相邻可通行格子之间的连接
权重：每条边的权重为 $1$

三、BFS解法的精妙实现

ACWing 走迷宫

3.1 关键数据结构

队列：存储待探索节点
方向数组：定义移动方向
访问标记：记录已访问节点（这里标记数组和迷宫地图可以进行公用）

#include <iostream>
#include <queue>
using namespace std;const int MAXN = 107; // 最大地图尺寸
int maze[MAXN][MAXN]; // 迷宫地图
int n, m;             // 迷宫行数和列数// 定义节点结构
struct Node {int x, y;   // 当前坐标int steps;  // 已走步数Node(int x, int y, int steps) : x(x), y(y), steps(steps) {}
};// 方向数组：右、左、下、上
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};// BFS求解最短路径
int bfs(int startX, int startY) {queue<Node> q;q.push(Node(startX, startY, 0));maze[startX][startY] = 1; // 标记起点已访问while (!q.empty()) {Node current = q.front();q.pop();// 到达终点if (current.x == n && current.y == m) {return current.steps;}// 尝试四个方向for (int i = 0; i < 4; i++) {int nx = current.x + dx[i];int ny = current.y + dy[i];// 检查新位置是否合法if (nx < 1 || ny < 1 || nx > n || ny > m || maze[nx][ny]) {continue;}maze[nx][ny] = 1; // 标记已访问q.push(Node(nx, ny, current.steps + 1));}}return -1; // 如果没有找到路径
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> maze[i][j];}}cout << bfs(1, 1) << endl;return 0;
}

3.2 核心优化技巧

即时标记：在入队时立即标记已访问，避免重复访问
提前终止：找到终点立即返回
边界检查：防止数组越界

四、复杂度分析与优化方向

4.1 时间复杂度

最坏情况： $O (n * m)$

4.2 空间复杂度

$O (n * m)$ （队列最大长度）

4.3 进阶优化思路

双向BFS：从起点和终点同时搜索
A*算法：结合启发式搜索
分层BFS：减少空间占用

五、BFS的广泛应用场景

最短路径：无权图的最短路径
连通性检测：判断图的连通性
状态空间搜索：解决八数码等问题
社交网络：计算人际关系距离

结语：算法之美的永恒追求

通过走迷宫问题，我们不仅掌握了BFS的精髓，更体会到算法设计中"简单与高效"的完美统一。从古老的迷宫谜题到现代的网络路由，BFS算法始终闪耀着智慧的光芒。当您下次面对复杂问题时，不妨想想这个简单的队列，它或许就是打开问题之门的钥匙。

思考题：如何修改算法使其可以输出具体的最短路径？
（tips:试着维护一个 $p$ 数组，记录每一个走过的节点的父节点试试呢）

广度优先搜索（BFS）算法详解——以走迷宫问题为例

引言：当算法遇见迷宫想象你置身于一个复杂的迷宫，如何在最短时间内找到出口？这个问题不仅存在于童话故事中，更是计算机科学中经典的路径搜索问题。本文将带你通过走迷宫问题，深入理解广度优先搜索（BFS&am…...

编程日记 2025/5/9 22:54:41

【大数据技术】用户行为日志分析（python+hadoop+mapreduce+yarn+hive）

用户行为日志分析（python+hadoop+mapreduce+yarn+hive）搭建完全分布式高可用大数据集群（VMware+CentOS+FinalShell）搭建完全分布式高可用大数据集群（Hadoop+MapReduce+Yarn）本机PyCharm远程连接虚拟机Python 搭建完全分布式高可用大数据集群（MySQL+Hive）...

编程日记 2025/5/9 14:13:28

C语言基础之【数组和字符串】（上）

C语言基础之【数组和字符串】（上） 概述一维数组一维数组的定义一维数组的初始化一维数组的访问一维数组的遍历数组名一维数组的常用数据强化训练一维数组的最值一维数组的逆置一维数组的排序（冒泡排序） 二维数组二维数组的定义二维…...

编程日记 2025/5/9 15:17:00

Maven插件—flatten-maven-plugin：工程模块统一版本依赖

文章目录前言一、认识flatten-maven-plugin插件二、如何使用flatten-maven-plugin插件？未使用flatten-maven-plugin插件之前的情况描述配置flatten-maven-plugin插件步骤1：最外层父模块安装插件&配置版本变量步骤2：各个自模块使用版本使…...

编程日记 2025/5/9 14:44:30

Linux系统环境变量

环境变量写在前面概念查看环境变量main函数的参数argc & argvenv bash环境变量写在前面对于环境变量，本篇主要介绍基本概念及三四个环境变量 —— PATH、HOME、PWD。其中 PATH 作为 “ 敲门砖 ”，我们会更详细讲解；理解环境变量的全局…...

编程日记 2025/5/9 14:26:29

TAPEX：通过神经SQL执行器学习的表格预训练

摘要近年来，语言模型预训练的进展通过利用大规模非结构化文本数据取得了巨大成功。然而，由于缺乏大规模高质量的表格数据，在结构化表格数据上应用预训练仍然是一个挑战。本文提出了TAPEX，通过在一个合成语料库上学习神经SQL执行…...

编程日记 2025/5/9 15:24:33

Ruby：从宝石到编程语言的奇妙联系(中英双语)

Ruby：从宝石到编程语言的奇妙联系在珠宝世界中，红宝石（Ruby）是一种象征热情、力量和高贵的珍贵宝石；而在编程世界中，Ruby则是一门灵活、优雅且富有创造力的编程语言。那么，这两者究竟有何联系…...

编程日记 2025/5/9 7:14:05

RLHF中的on-policy和off-policy的区别

在LLM（大语言模型）和RLHF（基于人类反馈的强化学习）中，on-policy和off-policy的主要区别在于数据的来源和策略更新的方式。以下是两者的详细对比以及各自的典型算法： On-policy 和 Off-policy 的区别特性…...

编程日记 2025/5/4 17:55:29

计算机考研复试上机02

目录 3、排序 1）排序（华中科技大学复试上机题） 2）成绩排序（清华大学复试上机题） 3）特殊排序（华中科技大学复试上机题） 4）整数奇偶排序（北京大学复试上机题） 5）小白鼠排队（北京大学复试上机题） 4、查找 1）找 x（哈尔滨工业大学复试上机题） 2）查找（北…...

编程日记 2025/5/9 15:10:38

利用ETL工具进行数据挖掘

ETL的基本概念数据抽取（Extraction）：从不同源头系统中获取所需数据的步骤。比如从mysql中拿取数据就是一种简单的抽取动作，从API接口拿取数据也是。数据转换（Transformation）：清洗、整合和转…...

编程日记 2025/5/8 23:13:14

02DevOps基础环境准备

准备两台Linux的操作系统，最简单的方式就是在本机上使用虚拟机搭建两个操作系统（实际生产环境是两台服务器，虚拟机的方式用于学习使用） 我搭建的两台服务器的ip分别是192.168.1.10、192.168.1.11 192.168.1.10服务器用于安装doc…...

编程日记 2025/5/6 17:49:26

一、Kafka 基础 1.1 创建topic kafka-topics.bat --bootstrap-server localhost:9092 --topic test --create 1.2 查看消费者偏移量位置 kafka-consumer-groups.bat --bootstrap-server localhost:9092 --describe --group test 1.3 消息的生产与发送 #生产者 kafka-cons…...

编程日记 2025/5/9 13:57:01

VM虚拟机安装群晖系统

下载群晖系统 https://download.csdn.net/download/hmxm6/90351935 安装群晖连接软件 synology-assistant-6.2-24922(在上面的压缩包里面) 准备好VM虚拟机创建群晖虚拟机打开下载下来的虚拟机添加硬盘选择类型创建新的磁盘指定容量指定存储文件完成硬盘添加…...

编程日记 2025/5/9 15:10:38

关于ESP-IDF 5.4 中添加第三方组件esp32-camera找不到文件，编译错误解决办法（花了一天时间解决）

最近需要使用ESP32-S3-CAM 的OV2640摄像头采集图像，为了加速开发进度，于是选择了esp32-camera组件，该组件不是官方组件，需要自己git clone。但在为项目添加esp32-camera组件时，一直编译错误，找不到头文件&a…...

编程日记 2025/5/9 15:41:39

【C++】C++11

目录 C11简介统一的列表初始化 {}初始化 std::initializer_list 声明 auto decltype nullptr 范围for循环智能指针 STL中的一些变化右值引用和移动语义左值引用和右值引用右值引用的意义完美转发 lambda表达式新的类功能可变参数模版包装器 func…...

编程日记 2025/5/9 14:41:03

Intellij IDEA如何查看当前文件的类

快捷键：CtrlF12，我个人感觉记快捷键很麻烦，知道具体的位置更简单，如果忘了快捷键（KeyMap）看一下就记起来了，不需要再Google or Baidu or GPT啥的，位置：Navigate > Fi…...

编程日记 2025/5/9 14:34:39

CF 278A.Circle Line

题目分析输入n个数据作为路径，求从a到b的最短距离，需要将其相成一个圆圈，既可以从小往大走又可以从大往小走思路分析依然将数据存为数组，通过下标进行操作，既然说了有两种方式那就计算两种方式哪个更快就输出谁代…...

编程日记 2025/5/9 14:34:39

Naive UI去掉n-select下拉框边框，去掉n-input输入框边框

1、第一种通过js去掉 <template><div><div style"margin-top:10px;width: 100%;"><dade-descriptions><tr><dade-descriptions-item label"代理名称"><dade-input placeholder"代理名称"></dade-…...

编程日记 2025/5/9 14:48:05

(文末提供数据集下载)ML.NET库学习001：基于PCA的信用卡异常检查之样本处理与训练

文章目录 (文末提供数据集下载)ML.NET库学习001：基于PCA的信用卡异常检查之样本处理与训练目标项目概述代码结构概述1. **主要类和文件**2. **命名空间和使用指令**3. **数据类 (TransactionObservation)**4. **主程序入口 (Main 方法)**5. **数据预处理 (DataPrepr…...

编程日记 2025/5/1 3:33:03

疯狂SQL转换系列- SQL for Milvs2.4

鉴于Milvus仍在不停的迭代新版本，推出新功能，其SDK目前并不稳定。目前其2.4版本的SDK接口已与之前的2.2版本有了较大的差别，功能上也有了一定的调整。为此，我们重新提供了针对[Milvus2.4](https://github.com/colorknight/moql-tr…...

编程日记 2025/5/9 14:45:20

C++的 I/O 流

本文把复杂的基类和派生类的作用和关系捋出来，具体的接口请参考相关文档 C的 I/O 流相关的类，继承关系如下图所示 https://zh.cppreference.com/w/cpp/io I / O 的概念：内存和外设进行数据交互称为 I / O ，例如：把数…...

编程日记 2025/5/1 3:32:47

基于ansible部署elk集群

ansible部署 ELK部署 ELK常见架构 （1）ElasticsearchLogstashKibana：这种架构是最常见的一种，也是最简单的一种架构，这种架构通过Logstash收集日志，运用Elasticsearch分析日志，最后通过Kibana中…...

编程日记 2025/5/9 15:20:42

4.Python字符串和列表：字符串输入、字符串输出、下标和切片、字符串常见函数、列表(list)、列表的循环遍历、列表的增删改查、列表的嵌套、列表的切片

1. Python 字符串 1.1 字符串输入 input() 函数用于从用户获取字符串输入。它总是返回一个字符串类型的值。 # 从用户输入字符串 name input("请输入你的名字：") print(f"你好, {name}")1.2 字符串输出字符串的输出通常使用 print() 函数…...

编程日记 2025/5/9 15:02:37

51单片机之使用Keil uVision5创建工程以及使用stc-isp进行程序烧录步骤

一、Keil uVision5创建工程步骤 1.点击项目，新建 2.新建目录 3.选择目标机器，直接搜索at89c52选择，然后点击OK 4.是否添加起吊文件，一般选择否 5.再新建的项目工程中添加文件 6.选择C文件 7.在C文件中右键，添加…...

编程日记 2025/5/9 15:19:42

Redis - 全局ID生成器 RedisIdWorker

文章目录 Redis - 全局ID生成器 RedisIdWorker一、引言二、实现原理三、代码实现代码说明四、使用示例示例说明五、总结 Redis - 全局ID生成器 RedisIdWorker 一、引言在分布式系统中，生成全局唯一ID是一个常见的需求。传统的自增ID生成方式在分布式环境下容易出…...

编程日记 2025/5/9 15:01:48

Linux ftrace 内核跟踪入门

文章目录 ftrace介绍开启ftraceftrace使用ftrace跟踪指定内核函数ftrace跟踪指定pid ftrace原理ftrace与stracetrace-cmd 工具KernelShark参考 ftrace介绍 Ftrace is an internal tracer designed to help out developers and designers of systems to find what is going on i…...

编程日记 2025/5/9 14:30:04

Visual Studio（VS）没有显示垂直滚轮or垂直滚轮异常显示

前言： 前段时间，我换上了新电脑。满心欢喜地安装好 VS，准备大干一场时，却发现了一个小麻烦 —— 垂直滚轮显示异常（如图 1）。这种显示方式实在让我难以适应，每一次操作都觉得别扭。于是&#…...

编程日记 2025/5/9 10:18:07

大数据数仓实战项目（离线数仓+实时数仓）3

1.课程内容和课程目标 2.订单时间维度指标需求分析根据时间数据，生成一个时间维度表，我们后面还可以去复用这个时间维度表 3.使用kettle生成日期维度数据 Hive创建日期维度表使用Kettle构建以下组件结构图使用kettle生成日期维度数据插入到我们的hi…...

编程日记 2025/5/9 15:52:33

通过acme生成与续签ssl证书，并部署到nginx

通过acme生成与续签ssl证书，并部署到nginx 介绍官方介绍： acme.sh 实现了 acme 协议，可以从 ZeroSSL，Lets Encrypt 等 CA 生成免费的证书。安装 acme.sh 1. curl方式 curl https://get.acme.sh | sh -s emailmyexample.com…...

编程日记 2025/5/9 15:17:00

c语言对应汇编写法（以中微单片机举例）

芯片手册资料 1. 赋值语句 C语言： a 5; b a; 汇编： ; 立即数赋值 LDIA 05H ; ACC 5 LD R01,A ; R01 ACC（a5）; 寄存器间赋值 LD A,R01 ; ACC R01（读取a的值） LD R02,A ; R02 ACC&…...

编程日记 2025/5/9 15:33:25

React基础内容（面试一）

React大厂常见的面试题目涉及多个方面，包括React的基本概念、组件、状态管理、生命周期、性能优化等。以下是对这些面试题目的详细解析： 一、React基本概念解释React是什么以及它的主要特点 React是一个用于构建用户界面的JavaScript库，由F…...

编程日记 2025/5/9 14:39:20

2025年软件测试五大趋势：AI、API安全、云测试等前沿实践

随着软件开发的不断进步，测试方法也在演变。企业需要紧跟新兴趋势，以提升软件质量、提高测试效率，并确保安全性，在竞争激烈的技术环境中保持领先地位。本文将深入探讨2025年最值得关注的五大软件测试趋势。 Parasoft下载https://…...

编程日记 2025/5/9 15:09:40

常用工具类——Collections集合框架

常用工具类——Collections集合框架 Collections 是 JDK 提供的一个工具类，提供了一系列静态方法，分类来复习！ 1.排序操作 reverse(List list) :反转顺序shuffle(List list) ： 洗牌，将顺序打乱sort(List list) &…...

编程日记 2025/5/9 14:06:05

【大数据技术】搭建完全分布式高可用大数据集群（ZooKeeper）

搭建完全分布式高可用大数据集群（ZooKeeper） apache-zookeeper-3.8.4-bin.tar.gz注：请在阅读本篇文章前，将以上资源下载下来。写在前面本文主要介绍搭建完全分布式高可用集群 ZooKeeper 的详细步骤。注意：统一约定将软件安装包存放于虚拟机的/software目录下，软件…...

编程日记 2025/5/9 14:15:19

Docker Desktop安装kubernetes时一直在Starting:Kubernetes failed to start

原因：由于墙的问题，导致拉取国外的K8s镜像失败解决： 下载 k8s-for-docker-desktop 选中自己的kubernetes 版本下载zip包 PowerShell运行load_images.ps1文件重启docker kubernetes运行成功...

编程日记 2025/4/24 22:37:28

物流中的物联网：其含义、应用和优势

随着世界联系日益紧密，物流格局正经历重大变革。科技已成为供应链管理的支柱，推动物流公司迈入效率与连通性兼具的新时代。物联网（IoT）是一股变革性力量，重塑着物流与运输行业的架构。物联网在物流领域并非昙花一现的…...

编程日记 2025/5/9 10:22:57

Axure设计教程：动态排名图（中继器实现）

一、开篇在Axure原型设计中，动态图表是展示数据和交互效果的重要元素。今天，我们将学习如何使用中继器来创建一个动态的排名图，该图表不仅支持自动轮播，还可以手动切换，极大地增强了用户交互体验。此教程旨在提供一个…...

编程日记 2025/5/9 15:19:42

【人工智能】掌握图像风格迁移：使用Python实现艺术风格的自动化迁移

《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门！解锁Python编程的无限可能：《奇妙的Python》带你漫游代码世界图像风格迁移（Image Style Transfer）是一种基于深度学习的计算机视觉技术，通过将一张图像的内容与另一张图像的艺术风格结合，生成一幅具…...

编程日记 2025/5/9 15:48:22

# C指针地址CUP寄存器访问IO内存映射

C指针地址&CUP寄存器访问&IO内存映射在裸机编程中，C语言可以像汇编语言一样直接操作芯片寄存器地址进行读取和写入，主要是由于以下几个原因： 1. 裸机环境下没有操作系统的干预裸机编程是指直接在硬件上运行程序，没有…...

编程日记 2025/5/9 15:29:25

UE5 蓝图学习计划 - Day 14：搭建基础游戏场景

在上一节中，我们确定了游戏类型，并完成了项目搭建、角色蓝图的基础设置（移动）。今天，我们将进一步完善游戏场景，搭建地形、墙壁、机关、触发器等基础元素，并添加角色跳跃功能，为…...

编程日记 2025/5/6 2:41:04

浅尝yolo11全程记录1-准备环境＋官网模型推理（个人备份）

准备工作（虚拟环境、导入项目） 安装Anaconda 主要是为了创建和管理虚拟环境，在pycharm里按照项目里的requirments.txt安装依赖的时候，使用虚拟环境会好很多（我记得不用Anaconda也可以直接在pycharm的terminal里头创建…...

编程日记 2025/5/1 1:23:17

用 Python 给 Excel 表格截图（20250207）

我搜索了网络上的方案，感觉把 Excel 表格转换为 HTML 再用 platwright 截图是比较顺畅的路径，因为有顺畅的工具链。如果使用的是 Windows 系统则不需要阅读此文，因为 win32com 库更方便。这篇文章中 Excel 转 HTML 的方案，主要弥补…...

编程日记 2025/5/9 14:58:55

Office/WPS接入DS等多个AI工具，开启办公新模式！

在现代职场中，Office办公套件已成为工作和学习的必备工具，其功能强大但复杂，熟练掌握需要系统的学习。为了简化操作，使每个人都能轻松使用各种功能，市场上涌现出各类办公插件。这些插件不仅提升了用户体验，…...

编程日记 2025/5/9 7:50:08

智能化转型2.0：从“工具应用”到“价值重构”

过去几年，“智能化”从一个模糊的概念逐渐成为企业发展的核心议题。2024年，随着生成式AI、大模型、智能体等技术的爆发式落地，中国企业正式迈入智能化转型的2.0时代。这一阶段的核心特征是从单一场景的“工具应用”转向全链条的“价值重构”&…...

编程日记 2025/5/9 14:58:55

深度整理总结MySQL——索引工作原理

B树索引数据结构前言什么样的索引数据结构是好的搜索速度要求支持范围查找寻求适合查找的算法寻求合适的数据结构二叉查找树自平衡二叉树B树B树数据结构B与B树比较总结前言相信你在面试时，通常会被问到“什么是索引？”而你一定要能脱口而出&#xf…...

编程日记 2025/5/9 15:00:50

基于asr的所见即可说方案

年前写的文章对所见即可说方案进一步调研-CSDN博客，针对rk3568定制版，进行了Accessibility实现所见即可说功能的验证与调研，结论是不可行。最终解决方案是：结合科大讯飞的AI大模型智能助手，使用rk3588板（…...

编程日记 2025/5/9 15:14:18

【截图】selenium自动通过浏览器截取指定元素div的图片

【截图】selenium自动通过浏览器截取指定元素div的图片思路截取完整网页截图通过元素的坐标截图到指定位置的图片前提是已经获取到 driver 了 # 定位目标divtarget_div driver.find_element(By.CLASS_NAME, headlines-right)# 获取div的位置和大小location target_div…...

编程日记 2025/5/9 15:14:18

CSS入门学习笔记（一）

学习视频：https://www.bilibili.com/video/BV1zN2UYoEEo/ 目录基本介绍语法引入方式内联样式（行内样式）内部样式外部样式选择器四种选择器全局选择器元素选择器类选择器id选择器合并选择器选择器的优先级字体属性colorfont-sizefont-weig…...