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

引言:当算法遇见迷宫

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


一、BFS算法原理剖析

1.1 BFS & DFS

在这里插入图片描述

1.2 算法核心思想

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

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

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

1.3 算法实现框架

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

1.4 算法特性分析

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

二、走迷宫问题建模

2.1 问题描述

给定一个 n ∗ m n*m nm的迷宫:

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

2.2 问题转化

将迷宫建模为图:

  • 节点:每个可通行的格子
  • :相邻可通行格子之间的连接
  • 权重:每条边的权重为 1 1 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 核心优化技巧

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

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

4.1 时间复杂度

  • 最坏情况: O ( n ∗ m ) O(n*m) O(nm)

4.2 空间复杂度

  • O ( n ∗ m ) O(n*m) O(nm)(队列最大长度)

4.3 进阶优化思路

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

五、BFS的广泛应用场景

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

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

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


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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/965935.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

kubeadm构建k8s源码阅读环境

目标 前面看了minikube的源码了解到其本质是调用了kubeadm来启动k8s集群&#xff0c;并没有达到最初看代码的目的。 所以继续看看kubeadm的代码&#xff0c;看看能否用来方便地构建源码调试环境。 k8s源码编译 kubeadm源码在k8s源码库中&#xff0c;所以要先克隆k8s源码。之…

BFS算法篇——广度优先搜索,探索未知的旅程(上)

文章目录 前言一、BFS的思路二、BFS的C语言实现1. 图的表示2. BFS的实现 三、代码解析四、输出结果五、总结 前言 广度优先搜索&#xff08;BFS&#xff09;是一种广泛应用于图论中的算法&#xff0c;常用于寻找最短路径、图的遍历等问题。与深度优先搜索&#xff08;DFS&…

baigeiRSA

baigeiRSA 打开附件有两个&#xff1a; 1.import libnumfrom Crypto.Util import numberfrom secret import flag​size 128e 65537p number.getPrime(size)q number.getPrime(size)n p*q​m libnum.s2n(flag)c pow(m, e, n)​print(n %d % n)print(c %d % c)​​2.n…

脚本一键生成管理下游k8s集群的kubeconfig

一、场景 1.1 需要管理下游k8s集群的场景。 1.2 不希望使用默认的cluster-admin权限的config. 二、脚本 **重点参数&#xff1a; 2.1 配置变量。 1、有单独namespace的权限和集群只读权限。 2、自签名的CA证书位置要正确。 2.2 如果配置错误&#xff0c;需要重新…

camera光心检测算法

1.概要 光心检测算法&#xff0c;基于opencv c实现&#xff0c;便于模组厂快速集成到软件工具中&#xff0c;适用于camera模组厂算法评估组装制程镜头与sensor的偏心程度&#xff0c;便于工程师了解制程的问题找出改善方向。 2.技术介绍 下图为camera模组厂抓取的bayer-raw经过…

基于logback+fastjson实现日志脱敏

一、需求背景 日常工作中&#xff0c;必不可免的会将一些敏感信息&#xff0c;如用户名、密码、手机号、身份证号、银行账号等等打印出来&#xff0c;但往往为了安全&#xff0c;这些信息都需要进行脱敏。脱敏实际就是用一些特殊字符来替换部分值。 JSON 和 JSONObject Fastj…

RC5分组加密算法

目录 &#xff08;1&#xff09;RC5密钥扩展算法 &#xff08;2&#xff09;RC5加密算法 &#xff08;3&#xff09;RC5解密算法 RC5分组加密算法 RC5分组密码算法是1994年RSA实验室的RonaldL.Rivest教授发明的。它是参数可变的分组密码算法&#xff0c;三个可变的参数是&a…

GPU — 8 卡 GPU 服务器与 NVLink/NVSwitch 互联技术

目录 文章目录 目录8 卡 GPU 服务器GPU 互联技术分类PCIe 直连PCIe Switch 互联NVLink 互联NVLink 1.0 与 DGX-1 系统NVLink 2.0 与 DGX-1 系统NVSwitch 全互联NVSwitch 1.0 与 DGX-2 系统NVLink 3.0、NVSwitch 2.0 与 DGX A100NVLink 4.0、NVSwitch 3.0 与 DGX H100NVSwitch v…

idea——IDEA2024版本创建Sping项目无法选择Java 8

目录 一、背景二、解决方式&#xff08;替换创建项目的源地址&#xff09; 一、背景 IDEA2024创建一个springboot的项目&#xff0c;本地安装的是1.8&#xff0c;但是在使用Spring Initializr创建项目时&#xff0c;发现版本只有17、21、23。 二、解决方式&#xff08;替换创…

STM32 串口发送与接收

接线图 代码配置 根据上一章发送的代码配置&#xff0c;在GPIO配置的基础上需要再配置PA10引脚做RX接收&#xff0c;引脚模式可以选择浮空输入或者上拉输入&#xff0c;在USART配置串口模式里加上RX模式。 配置中断 //配置中断 USART_ITConfig(USART1, USART_IT_RXNE, ENABLE…

储能系统-系统架构

已更新系列文章包括104、61850、modbus 、单片机等&#xff0c;欢迎关注 IEC61850实现方案和测试-1-CSDN博客 快速了解104协议-CSDN博客 104调试工具2_104协议调试工具-CSDN博客 1 电池储能系统&#xff08;BESS&#xff09; 架构 电池储能系统主要包括、电池、pcs、本地控制…

TOTP实现Google Authenticator认证工具获取6位验证码

登录遇到Google认证怎么办? TOTP是什么?(Google Authenticator) TOTP(Time-based One-Time Password)是一种基于时间的一次性密码算法,主要用于双因素身份验证。其核心原理是通过共享密钥和时间同步生成动态密码,具体步骤如下: 共享密钥:服务端与客户端预先共享一个…

清理服务器/docker容器

清理服务器 服务器或docker容器清理空间。 清理conda环境 删除不用的conda虚拟环境&#xff1a; conda env remove --name python38 conda env remove --name python310清理临时目录&#xff1a;/tmp du -sh /tmp # 查看/tmp目录的大小/tmp 目录下的文件通常是可以直接删除…

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

<template><div><div style"margin-top:10px;width: 100%;"><dade-descriptions><tr><dade-descriptions-item label"代理名称"><dade-input placeholder"代理名称"></dade-input></dade-de…

【完整版】DeepSeek-R1大模型学习笔记(架构、训练、Infra)

文章目录 0 DeepSeek系列总览1 模型架构设计基本参数专家混合模型&#xff08;MoE&#xff09;[DeepSeek-V2提出, DeepSeek-V3改良]多头潜在注意力&#xff08;MLA&#xff09;[DeepSeek-V2提出]多token预测&#xff08;MTP&#xff09;[DeepSeek-V3提出] 2 DeepSeek-R1-Zero及…

如何使用 Python 和 SQLAlchemy 结合外键映射来获取其他表中的数据

在使用 Python 和 SQLAlchemy 时&#xff0c;结合外键映射可以让你在查询时轻松地获取其他表中的数据。SQLAlchemy 提供了丰富的 ORM&#xff08;对象关系映射&#xff09;功能&#xff0c;可以让你通过定义外键关系来查询并获取关联的数据。下面我会演示如何设置外键关系&…

Python爬虫:1药城店铺爬虫(完整代码)

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…

游戏引擎学习第91天

黑板&#xff1a;澄清线性独立性 首先&#xff0c;提到线性独立时&#xff0c;之前讲解过的“最小”的概念实际上是在表达线性独立。对于二维坐标系来说&#xff0c;两个基向量是最小的&#xff0c;这两个向量是线性独立的。如果超过两个基向量&#xff0c;就会变得冗余&#…

学习率调整策略 | PyTorch 深度学习实战

前一篇文章&#xff0c;深度学习里面的而优化函数 Adam&#xff0c;SGD&#xff0c;动量法&#xff0c;AdaGrad 等 | PyTorch 深度学习实战 本系列文章 GitHub Repo: https://github.com/hailiang-wang/pytorch-get-started 本篇文章内容来自于 强化学习必修课&#xff1a;引…

在 Flownex 中创建自定义工作液

在这篇博文中&#xff0c;我们将了解如何在 Flownex 中为流网添加和定义一种新的流体温度相关工作材料。 Flownex 物料管理界面 在 Flownex 中使用与温度相关的流体材料时&#xff0c;了解其特性与温度的关系非常重要。这种了解可确保准确预测各种热条件下的流体行为&#xff0…