深度优先搜索(DFS)与广度优先搜索(BFS):探索图与树的算法

一、引言

        在图论和树形结构中,搜索算法是寻找从起点到终点的路径的关键。其中,深度优先搜索DFS和广度优先搜索BFS是最常用且最基础的两种搜索算法。本文将详细介绍广度优先搜索BFS的原理、应用场景,并通过代码示例来展示其实现。

 

二、广度优先搜索(BFS)简介

        广度优先搜索(BFS)是一种用于遍历或搜索树或图的算法。它从根(或任意节点)开始,探索最近的节点,然后进行下一层的邻居节点,逐层向外扩展。这种策略使得BFS能够首先找到从起始点到目标点的最短路径(如果存在的话)。

三、BFS算法步骤

  • 创建一个队列,并将起始节点入队。
  • 从队列中取出一个节点,并检查它是否为目标节点。如果是,则搜索结束,返回路径。
  • 如果不是目标节点则将其所有未访问过的邻居节点入队并标记这些邻居节点为已访问。
  • 重复步骤2和3,直到队列为空或者找到目标节点。

四、BFS的应用场景

  • 最短路径问题:在图中查找从源点到目标点的最短路径。
  • 图的遍历:访问图中的所有节点。
  • 迷宫求解:在迷宫中找到从起点到终点的路径。

五、BFS代码示例(Python)

下面是一个简单的BFS实现,用于在无向图中搜索路径:

from collections import deque  
  
def bfs(graph, start, end):  
    visited = set()  
    queue = deque([start])  
      
    while queue:  
        vertex = queue.popleft()  
          
        if vertex == end:  
            return True  
          
        for neighbour in graph[vertex]:  
            if neighbour not in visited:  
                visited.add(neighbour)  
                queue.append(neighbour)  
                  
    return False  
  
# 示例图(使用邻接表表示)  
graph = {  
    'A': ['B', 'C'],  
    'B': ['A', 'D', 'E'],  
    'C': ['A', 'F'],  
    'D': ['B'],  
    'E': ['B', 'F'],  
    'F': ['C', 'E'],  
}  
  
# 测试BFS函数  
print(bfs(graph, 'A', 'F'))  # 输出: True  
print(bfs(graph, 'A', 'D'))  # 输出: True  
print(bfs(graph, 'A', 'G'))  # 输出: False

        在这个示例中,我们定义了一个bfs函数,它接受一个图(以邻接表形式表示)、一个起始节点和一个目标节点作为输入。函数使用队列来存储待访问的节点,并使用一个集合来跟踪已访问的节点。如果找到目标节点,函数返回True;否则,返回False


 六、结论

        广度优先搜索(BFS)是一种强大的图遍历算法,它在许多应用场景中都发挥着重要作用。通过理解BFS的原理和实现,我们可以更好地解决图论中的各种问题,如最短路径、图的遍历和迷宫求解等。

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

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

相关文章

CVE-2022-25487 漏洞复现

漏洞描述:Atom CMS 2.0版本存在远程代码执行漏洞,该漏洞源于/admin/uploads.php 未能正确过滤构造代码段的特殊元素。攻击者可利用该漏洞导致任意代码执行。 其实这就是一个文件上传漏洞罢了。。。。 打开之后,/home路由是个空白 信息搜集&…

分享88个鼠标特效,总有一款适合您

分享88个鼠标特效,总有一款适合您 88个鼠标特效下载链接:https://pan.baidu.com/s/1ljcxwgXGpw7baiufUGJjZA?pwd8888 提取码:8888 Python采集代码下载链接:采集代码.zip - 蓝奏云 学习知识费力气,收集整理更不…

C++之继承

一,概念及用法 1)概念 首先我们来了解一下官方的概念:继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段,它允许程序员在保持原有类特性的基础上进行扩展,增加功能,这样产生新的类&a…

【Linux学习】线程详解

目录 十八.多线程 18.1 线程与进程 18.2 内核视角看待创建线程与进程 18.3 线程优缺点总结 线程的优点: 线程的缺点: 线程的用途: 18.4 线程与进程的联系 十九.线程控制 19.1 POSIX线程库 19.2 线程创建 19.3 线程等待 19.4 线程终止 19.5 线…

C# OCR识别图片中的文字

1、从NuGet里面安装Spire.OCR 2、安装之后,找到安装路径下,默认生成的packages文件夹,复制该文件夹路径下的 6 个dll文件到程序的根目录 3、调用读取方法 OcrScanner scanner new OcrScanner(); string path "C:\1.png"; scann…

原来你也可以DDOS?

首先祝大家新年快乐 这次内容就主要是纸上谈兵(因为无法未经试验无法保证成功),而且有关这方面的科普视频也已经有很多了。 原文地址:原来你也可以DDOS? - Pleasure的博客 下面是正文内容: 前言 DDOS是一…

Hive SQL编译成MapReduce任务的过程

一、 Hive 底层执行架构 1.1 Hive底层架构 1 )用户接口: Client CLI ( command-line interface )、 JDBC/ODBC(jdbc 访问 hive) 、 WEBUI (浏览器访问 hive ) 2 )元数据: Metas…

mxxWechatBot流程与原理

大家伙,我是雄雄,欢迎关注微信公众号:雄雄的小课堂。 免责声明:该工具仅供学习使用,禁止使用该工具从事违法活动,否则永久拉黑封禁账号!!!本人不对任何工具的使用负责&am…

高级自定义标记功能

高级自定义标记功能 自定义标记时用户定义的标记,它可通过创建可重用的组件来尽量较少JSP中复杂、重复的业务逻辑代码。这些组件可用于其他应用程序。Javax.servlet.jsp.tagtext包定义了开发自定义标记的类和接口。您可以使用此包的类和接口创建标记处理程序,这些程序可实现带…

matlab发送串口数据,并进行串口数据头的添加,我们来看下pwm解析后并通过串口输出的效果

uintt16位的话会在上面前面加上00,16位的话一定是两个字节,一共16位的数据 如果是unint8的话就不会, 注意这里给的是13,但是现实的00 0D,这是大小端的问题,在matlanb里设置,我们就默认用这个模式…

面了滴滴的数据分析师(实习),几道面试题都是原题啊。。。

年前,技术群组织了一场数据类的技术&面试讨论会,邀请了一些同学分享他们的面试经历,讨论会会定期召开,如果你想加入我们的讨论群或者希望要更详细的资料,文末加入。 喜欢本文记得收藏、关注、点赞 。技术交流文末…

Unity类银河恶魔城学习记录7-2 P68 Setting up details of sword源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释,可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili Sword_Skill.cs using System.Collections; using System.Collections.Gen…

【数据结构】14 队列(带头结点的链式存储和顺序存储实现)

定义 队列是一个有序线性表,但是队列的插入、删除操作是分别在线性表的两个不同端点进行的。 设一个队列 Q ( a 1 , a 2 , . . . , a n ) Q (a_1, a_2,...,a_n) Q(a1​,a2​,...,an​),那么 a 1 a_1 a1​被称为队头元素, a n a_n an​为队…

【实战】一、Jest 前端自动化测试框架基础入门 —— 前端要学的测试课 从Jest入门到TDD BDD双实战(一)

文章目录 一、前端要学的测试课1.前端要学的测试2.前端工程化的一部分3.前端自动化测试的例子4.前端为什么需要自动化测试?5.课程涵盖内容6.前置技能7.学习收获 二、Jest 前端自动化测试框架基础入门1. 自动化测试背景及原理前端自动化测试产生的背景及原理 2.前端自…

Javaweb之SpringBootWeb案例之事务进阶的详细解析

1.3 事务进阶 前面我们通过spring事务管理注解Transactional已经控制了业务层方法的事务。接下来我们要来详细的介绍一下Transactional事务管理注解的使用细节。我们这里主要介绍Transactional注解当中的两个常见的属性: 异常回滚的属性:rollbackFor 事…

springboot179基于javaweb的流浪宠物管理系统的设计与实现

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计,课程设计参考与学习用途。仅供学习参考, 不得用于商业或者非法用途,否则,一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…

【C++】STL之string 超详解

目录 1.string概述 2.string使用 1.构造初始化 2.成员函数 1.迭代器 2.容量操作 1.size和length 返回字符串长度 2.resize 调整字符串大小 3.capacity 获得字符串容量 4.reserve 调整容量 5.clear 清除 6.empty 判空 3.string插入、追加 、拼接 1.运算…

【MySQL】MySQL函数学习和总结

🌈个人主页: Aileen_0v0 🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​💫个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-Ny0xnYjfHqF7s3aS {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…

【DDD】学习笔记-精炼领域分析模型

通过统一语言与“名词动词法”可以迫使团队研究问题域的词汇表,简单而快速地帮助我们获得初步的分析模型。但是这种方法获得的模型品质,受限于语言描述的写作技巧,统一语言的描述更多体现在是对现实世界的模型描述,缺乏深入精准的…

招商证券流年不利:屡因保荐失职“连坐”,各业务分部收入下滑

近日,安徽证监局发布公告称,招商证券股份有限公司(下称“招商证券”)“15城六局”债券的受托管理方面存在未督导发行人做好募集资金管理、未持续跟踪和监督发行人履行有关信披临时报告义务等情形。 根据《公司债券发行与交易管理…