深度优先搜索(DFS):探索图与树的深度之旅

引言

        在图论和计算机科学中,深度优先搜索(DFS)是一种用于遍历或搜索树或图的算法。与广度优先搜索(BFS)不同,DFS沿着树的深度遍历树的节点,尽可能深地搜索树的分支。在图中,这种策略可以用于寻找从起始节点到目标节点的路径,或者简单地遍历图中的所有节点。


DFS算法原理

        深度优先搜索(DFS)算法使用堆栈(或递归)来存储需要探索的节点。算法从根节点(或任意节点)开始,沿着树的深度进行搜索,直到达到目标节点或遍历完所有可到达的节点。

以下是DFS算法的基本步骤:

  • 创建一个空堆栈,并将起始节点压入堆栈。
  • 当堆栈不为空时,从堆栈顶部弹出一个节点,并检查它。
  • 将该节点的所有未访问过的邻居节点压入堆栈。
  • 重复步骤2和3,直到找到目标节点或堆栈为空。

        需要注意的是,在实际实现中,我们通常使用递归而不是堆栈来执行DFS,因为递归可以更简洁地表达深度优先的遍历过程。

DFS的应用场景

深度优先搜索(DFS)在计算机科学中有广泛的应用,包括:

  • 图的遍历:访问图中的所有节点,确保每个节点都被访问一次。
  • 路径查找:在图中查找从起始节点到目标节点的路径。
  • 连通性检查:检查无向图中的两个节点是否连通。
  • 拓扑排序:对有向无环图(DAG)进行排序,以确定节点之间的先后关系。
  • 生成树和生成森林:从图中生成深度优先搜索树或森林。
  • DFS代码示例(Python)

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

def dfs(graph, start, end, visited=None):  
    if visited is None:  
        visited = set()  
      
    # 创建一个用于模拟递归调用的堆栈  
    stack = [(start, [start])]  
      
    while stack:  
        (vertex, path) = stack.pop()  
          
        # 检查当前节点是否为目标节点  
        if vertex == end:  
            return path  
          
        # 遍历当前节点的邻居节点  
        for neighbour in graph[vertex]:  
            if neighbour not in visited:  
                # 将邻居节点标记为已访问,并将其压入堆栈以进行进一步探索  
                visited.add(neighbour)  
                stack.append((neighbour, path + [neighbour]))  
                  
    # 如果遍历完所有节点仍未找到目标节点,则返回None  
    return None  
  
# 示例图(使用邻接表表示)  
graph = {  
    'A': ['B', 'C'],  
    'B': ['A', 'D', 'E'],  
    'C': ['A', 'F'],  
    'D': ['B'],  
    'E': ['B', 'F'],  
    'F': ['C', 'E'],  
}  
  
# 测试DFS函数  
print(dfs(graph, 'A', 'F'))  # 输出可能是: ['A', 'C', 'F'] 或者其他有效路径(取决于遍历顺序)  
print(dfs(graph, 'A', 'D'))  # 输出: ['A', 'B', 'D']  
print(dfs(graph, 'A', 'G'))  # 输出: None(图中不存在从A到G的路径)

        在这个示例中,我们定义了一个dfs函数,它接受一个图(以邻接表形式表示)、一个起始节点、一个目标节点以及一个可选的已访问节点集合。我们使用一个堆栈来模拟递归调用,堆栈中的每个元素都是一个包含当前节点和从起始节点到当前节点的路径的元组。函数通过不断弹出堆栈顶部的元素并探索其邻居节点来执行深度优先搜索。如果找到目标节点,则返回从起始节点到目标节点的路径;否则,返回None。

  •         然而,上面的代码实际上并不是标准的递归DFS实现,而是使用堆栈模拟了递归的过程。下面是一个更标准的递归DFS实现:
def dfs_recursive(graph, start, end, visited=None):  
    if visited is None:  
        visited = set()  
          
    # 检查起始节点是否为目标节点  
    if start == end:  
        return [start]  
      
    visited.add(start)  
      
    # 递归遍历起始节点的所有邻居节点  
    for neighbour in graph[start]:  
        if neighbour not in visited:  
            path

总结

        深度优先搜索(DFS)是一种强大的图遍历算法,适用于许多不同的问题。通过递归或堆栈实现DFS,可以轻松地找到从起始节点到目标节点的路径,或者遍历图中的所有节点。在实际应用中,DFS的效率和可读性都非常重要,因此选择合适的实现方式(递归或迭代)取决于具体的需求和上下文。

 

 

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

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

相关文章

文心一言 VS 讯飞星火 VS chatgpt (197)-- 算法导论14.3 5题

五、用go语言,对区间树 T 和一个区间 i ,请修改有关区间树的过程来支持新的操作 INTERVALSEARCH-EXACTLY(T,i) ,它返回一个指向 T 中结点 x 的指针,使得 x.int. lowi.low 且 x.int.high i.high ;或者,如果…

华为第二批难题五:AI技术提升六面体网格生成自动化问题

有CAE开发商问及OCCT几何内核的网格方面的技术问题。其实,OCCT几何内核的现有网格生成能力比较弱。 HybridOctree_Hex的源代码,还没有仔细去学习。 “HybridOctree_Hex”的开发者说:六面体网格主要是用在数值模拟领域的,比如汽车…

LabVIEW网络测控系统

LabVIEW网络测控系统 介绍了基于LabVIEW的网络测控系统的开发与应用,通过网络技术实现了远程的数据采集、监控和控制。系统采用LabVIEW软件与网络通信技术相结合,提高了系统的灵活性和扩展性,适用于各种工业和科研领域的远程测控需求。 随着…

8个简约精美的WordPress外贸网站主题模板

Simplify WordPress外贸网站模板 Simplify WordPress外贸网站模板,简洁实用的外贸公司wordpress外贸建站模板。 查看演示 Invisible Trade WP外贸网站模板 WordPress Invisible Trade外贸网站模板,做进出口贸易公司官网的wordpress网站模板。 查看演…

微信小程序(基本操作)

概念: 小程序:就是小程序,mini program。现在市面上有微信小程序,百度智能小程序等等。 微信小程序,简称小程序,英文名Mini Program,是一种不需要下载安装即可使用的应用,它实现了…

Python进程之串行与并行

串行和并行 串行指的是任务的执行方式。串行在执行多个任务时,各个任务按顺序执行,完成一个之后才能进行下一个。(早期单核CPU的情况下) 并行指的是多个任务在同一时刻可以同时执行(前提是多核CPU)&#…

【蓝桥杯单片机记录】IO基础与LED控制

目录 一、IO基础 1.1 IAP15F2K61S2芯片原理图 1.2不同工作模式 二、新建工程的一些补充 2.1 keil中没有IAP15F2K61S2的头文件 解决:在isp软件中找到如下​编辑 2.2keil中的芯片选择 2.3推荐字体 三、sbit关键字 四、LED控制 4.1原理图 4.2不能直接通过IO…

电脑多出一个虚拟驱动器又无法删除怎么办

下载解压UltraISO https://wwb.lanzoum.com/i8vY71nqnp4d 右键UltraISO.exe以管理员身份运行 点击选项 点击配置 91fddbd892a0.png) 点击虚拟光驱,把设备数量改成无,点击确定即可

Spring是怎么解决循环依赖的

首先先解释一下什么叫循环依赖 循环依赖:循环依赖其实就是循环引用,也就是两个或两个以上的bean互相持有对方,最终形成闭环.比如A依赖于B,B依赖于A 循环依赖在spring中是允许存在的,spring框架依据三级缓存已经解决了大部分的循环依赖 一级缓存:单例池,缓存已经经历了完整的…

门诊单据打印用什么软件,线下处方单生成系统教程

门诊单据打印用什么软件,线下处方单生成系统教程 一、前言 以下软件教程以 佳易王诊所电子处方管理系统软件V17.3为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 如上图,电子处方或病历记录开单生成保存后,可…

3分钟部署完成Docker Registry及可视化管理工具Docker-UI

安装docker-registry 由于镜像文件会非常占用空间,因此需要选择一个磁盘充裕的位置来存放镜像数据。 这里设置为:-v /data/registry:/var/lib/registry,其中/data/registry是宿主机存放数据的位置。 docker run -d -p 5000:5000 --restart…

95.网游逆向分析与插件开发-游戏窗口化助手-窗口化助手显示与大小调整

内容参考于:易道云信息技术研究院VIP课 上一个内容:地图数据获取的逆向分析与C代码还原 码云地址(游戏窗口化助手 分支):https://gitee.com/dye_your_fingers/sro_-ex.git 码云版本号:e85c0fc8b85895c8c…

深度分析一款新型Linux勒索病毒

前言 DarkRadiation勒索病毒是一款全新的Linux平台下的勒索病毒,2021年5月29日首次在某平台上发布了此勒索病毒的相关的信息,6月中旬趋势科技针对这个新型的勒索病毒进行了相关的分析和报道。 DarkRadiation勒索病毒采用Bash脚本语言编写实现&#xff0…

运维高级篇-分库分表(拆分策略详解)

分库分表 介绍 问题分析 随着互联网及移动互联网的发展,应用系统的数据量也是成指数式增长,若采用单数据库进行数据存 储,存在以下性能瓶颈: IO瓶颈:热点数据太多,数据库缓存不足,产生大量磁盘…

Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组

两数之和 —— 无序数组 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现…

SCI 1区论文:Segment anything in medical images(MedSAM)[文献阅读]

基本信息 标题:Segment anything in medical images中文标题:分割一切医学图像发表年份: 2024年1月期刊/会议: Nature Communications分区: SCI 1区IF:16.6作者: Jun Ma; Bo Wang(一作;通讯)单位:加拿大多…

「Mybatis实战五」:Mybatis核心文件详解 - MyBatis常用配置environments、properties

一、MyBatis核心配置文件层级关系 ​ 本文代码在 Mybatis初体验:一小时从入门到运行你的第一个应用 所构建的基础代码结构之上,进行修改。 MyBatis 的配置文件包含了会深深影响 MyBatis 行为的设置和属性信息。 配置文档的顶层结构如下: 二…

【C语言初阶-结构体】关于结构体的声明定义、结构体传参详解

目录 1. 结构体的声明 1.1 结构的基础知识 1.2 结构的声明 1.3 结构成员的类型 1.4 结构体变量的定义和初始化 2. 结构体成员的访问 2.1(.)操作符 2.2(->)操作符 3.结构体传参 1. 结构体的声明 1.1 结构的基础知识 结构体是一些值的集合&…

K8S之Pod常见的状态和重启策略

Pod常见的状态和重启策略 常见的Pod状态PendingPodScheduledUnschedulablePodInitializingImagePullBackOffInitializedRunningErrorCrashLoopBackOffTerminatingSucceededFailedEvictedUnknown Pod的重启策略使用Always重启策略使用Never重启策略使用OnFailure重启策略(常用) …

【经验】SPICE仿真 - Bob Pease会说No吗?

每一个读过我博客的人都知道,我使用SPICE模型仿真电路。你可能听说过Bob Pease,在SPICE领域相当执有己见,他曾经说过:“SPCIE模型削弱了你对所发生事物的洞察能力。SPICE模型实际上降低了你对电路如何工作的理解能力”。今天&…