【算法】浅析深度优先搜索算法
深度优先搜索算法:深入探索,穷尽可能
1. 引言
在计算机科学中,深度优先搜索(Depth-First Search,简称DFS)是一种用于遍历或搜索树或图的算法。这种算法会沿着一个分支走到底,直到这个分支结束,然后回溯到上一个分叉点,继续探索下一个分支。本文将介绍深度优先搜索算法的原理、实现方法及其在实际应用中的重要性,并通过代码示例和图示帮助大家更好地理解。
2. 深度优先搜索算法简介
2.1 定义
深度优先搜索是一种优先遍历子节点,直到达到某个条件后回溯的算法。
2.2 特点
(1)递归:通过递归函数实现节点间的遍历。
(2)回溯:当达到某个节点没有子节点时,返回上一个节点继续寻找其他路径。
(3)标记:通常需要对访问过的节点进行标记,以避免重复访问。
3. 深度优先搜索算法原理
深度优先搜索的核心思想是沿着一个路径深入到不能再深入为止,然后回溯到上一个分叉点,继续探索下一条路径。
3.1 示例:图的遍历
图的深度优先搜索是一种经典的DFS应用,其基本思想是从一个顶点开始,探索尽可能深的分支,当该分支结束,回溯到上一个顶点,继续探索其他分支。
3.2 代码示例(Python)
def dfs(graph, node, visited):if node not in visited:print(node)visited.add(node)for neighbour in graph[node]:dfs(graph, neighbour, visited)
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []
}
visited = set()
dfs(graph, 'A', visited)
输出结果:A B D E C F
4. 图示理解
以下通过图示来帮助大家理解深度优先搜索算法。
4.1 图的遍历
假设我们有以下无向图,我们将使用DFS进行遍历:
A/ \B C| |D F\ /E
4.1.1 遍历步骤
- 从顶点A开始,访问A。
- 探索A的邻接点,访问B。
- B有邻接点D和E,首先访问D。
- D没有未访问的邻接点,回溯到B,访问E。
- E访问了F,F没有未访问的邻接点,回溯到E,再回溯到B。
- B的邻接点已全部访问,回溯到A。
- A的下一个邻接点是C,访问C。
- C的邻接点F已访问,回溯到C,再回溯到A。
- 所有顶点已访问,遍历结束。
4.2 遍历顺序
遍历顺序为:A -> B -> D -> E -> F -> C
5. 深度优先搜索算法的使用
5.1 适用场景
深度优先搜索算法适用于以下类型的问题:
(1)需要遍历树或图的全部顶点。
(2)需要找到从起点到终点的路径。
(3)需要检测图中的环或连通性。
5.2 常见应用
- 拓扑排序:一种对有向无环图进行排序的算法。
- 路径搜索:在图中寻找两个顶点之间的路径。
- 棋盘游戏:如国际象棋、围棋等,探索所有可能的走法。
- 寻找连通分量:在无向图中找到所有连通的子图。
5.3 代码示例:路径搜索
以下代码示例展示了如何使用DFS在图中寻找路径。
def dfs_path(graph, start, end, path, visited):path.append(start)if start == end:return pathvisited.add(start)for neighbour in graph[start]:if neighbour not in visited:new_path = dfs_path(graph, neighbour, end, path, visited)if new_path:return new_pathpath.pop()return None
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []
}
visited = set()
print("路径:", dfs_path(graph, 'A', 'F', [], visited))
输出结果:路径:[‘A’,‘B’, ‘D’, ‘E’, ‘F’]
6. 深度优先搜索算法的意义
- 探索所有可能:DFS能够探索所有可能的路径,这对于解决某些类型的问题(如迷宫问题、棋盘游戏等)非常有用。
- 检测连通性:在图论中,DFS可以用来检测图的连通性,包括找出所有的连通分量。
- 简化问题:通过递归的方式,DFS可以将复杂的问题简化为更小的子问题,使得问题更容易处理。
- 高效的空间利用:DFS不需要存储所有可能的节点组合,因此相比宽度优先搜索(BFS),它在空间上更加高效。
7. 总结
深度优先搜索算法作为一种强大的搜索策略,在解决树和图相关问题中具有广泛的应用。通过本文的介绍,相信大家对DFS的原理、实现和应用有了更深入的认识。在实际问题求解过程中,我们可以根据问题的特点,合理选择和运用DFS,以有效地解决问题。
8. 扩展阅读
- 宽度优先搜索(BFS):与DFS不同,BFS优先探索最近的节点,常用于找到最短路径。
- 回溯算法:一种通过尝试所有可能的组合来找到问题解的算法,DFS常常与回溯算法结合使用。
- 分支限界法:一种在解决问题时,通过限界函数来剪枝,避免不必要的搜索的算法。
- 动态规划:一种在解决多阶段决策问题时,通过保存子问题的解来避免重复计算的算法。
通过了解这些算法,可以更好地理解各种算法之间的联系和区别,并在实际问题中选择最适合的算法。
相关文章:
【算法】浅析深度优先搜索算法
深度优先搜索算法:深入探索,穷尽可能 1. 引言 在计算机科学中,深度优先搜索(Depth-First Search,简称DFS)是一种用于遍历或搜索树或图的算法。这种算法会沿着一个分支走到底,直到这个分支结束…...

鸿蒙系统开发【ASN.1密文转换】安全
ASN.1密文转换 介绍 本示例对使用kit.CryptoArchitectureKit加密后的密文格式进行转换。kit.CryptoArchitectureKit加密后的密文格式默认为以base64显示的ASN.1格式问题,通过对密文进行base64变换后得到字符数组,以16进制数字显示,再此基础…...
【期末复习】软件质量保证与测试
考试内容 a卷 前三个部分(就业前景、岗位、发展前景(第一部分最后一个知识点),第四部分缺陷管理不考) 单选 10*2 判断 12*1 简单3*10 四个小题 (7个 pta部分涵盖+ppt) 设计 10+18 简答题(PTA简答题+PPT) 背完80分以上基本没问题 一、什么是软件。 软件是计算…...

CTFHub——XSS——反射型
1、反射型: 发现为表单式,猜测哪个可能存在注入漏洞,分别做测试注入发现name框存在xss漏洞 输入发现有回显但不是对方cookie,参考wp发现要用xss线上平台 将xss平台测试语句注入,将得到的url编码地址填入url框…...
docker 部署 libreoffice
创建 jdk 镜像 1、创建 Dockfile 文件 FROM centos:7 ADD jdk-8u212-linux-x64.tar.gz /usr/local RUN mv /usr/local/jdk1.8.0_212 /usr/local/jdk ENV JAVA_HOME=/usr/local/jdk ENV JRE_HOME=$JAVA_HOME/jre ENV CLASSPATH=$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATH ENV P…...
预测各种开发语言的市场占比
预测各种开发语言的市场占比是一个复杂且动态的任务,因为它受到多种因素的影响,包括市场需求、技术趋势、项目类型、开发团队的经验和偏好等。然而,我可以根据当前的技术趋势、编程语言排行榜以及市场需求情况,给出一个大致的预测…...
mybatisplus 通用字段自动赋值与更新
1、数据库级别的自动赋值与更新 比如自动更新时间和插入时间 default current_timestamp 插入的时候获取当前 default current_timestamp on update current_timestamp 修改的时候更新时间 无法用数据库更新的通用字段 借助 mybatisplus 的 metaobjecthandler 实现metaob…...

图像生成中图像质量评估指标—FID介绍
文章目录 1. 背景介绍2. 实际应用3. 总结和讨论 1. 背景介绍 Frchet Inception Distance(\textbf{FID})是一种衡量生成模型性能的指标,它基于Inception网络提取的特征来计算模型生成的图像与真实图像集合之间的距离。 FID利用了Inception模…...

uniapp全局分享功能实现方法(依赖小程序右上角的分享按钮)
1、uniapp开发小程序时默认是关闭分享功能的。点击右上角三个点可查看,效果图如下: 2、在utils文件夹下新建share.js文件,名字任起。(使用的是全局分享,因为一个一个页面的去分享太麻烦且没必要。) export…...
Redis中BigKey的判定查找建议
判定依据 key本身的数据量过大:string类型的key它的值为5MBkey中的成员数量过多:一个zset类型的key成员数量为10000个key中的成员数据量过大:一个hash类型的key他的成员只有1000个但是这些value总大小超过100MB查看内存命令 127.0.0.1:6379> hset k1 name 123 age 123 sex…...
Swift-语法基础
一、声明 变量声明 以关键字 var 开头的声明引入变量,该变量在程序执行期间可以具有不同的值。 var str: String "hello" str "hello, world" 常量声明 以关键字 let 开头的声明引入只读常量,该常量只能被赋值一次。 let s…...
面向对象进阶:多态、内部类、常用API
目录 Java中的接口 Java中的内部类 常用API StringBuilder类 Java高级面向对象编程 在这篇博客文章中,我们将探索Java中的高级面向对象编程概念,包括接口、内部类和常用API。每个概念都将通过代码示例来演示它们的应用。 Java中的接口 什么是接口&…...
寸(英寸)、码、斤、公顷等日常中大概的换算单位你清楚吗
这些单位和概念是我们日常生活和工作中不可或缺的部分,理解它们的用途和转换关系可以让我们更有效地处理信息、进行交流和解决问题。 1、寸(英寸) 1寸(或英寸)等于0.0254米,2寸等于:20.0254&a…...

Python面试宝典第26题:最长公共子序列
题目 一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。比如:"ace" 是 "abcde" 的子序列,但 "…...

接口测试学习笔记2
一、复习和扩展: 1、金字塔测试模型 UI测试 -- 黑盒 Service 服务层--函数之间的调用 灰盒 接口测试 Unit单元层--白盒测试 趋势:逐步向下发展 测试优先、测试驱动 -- 先考虑怎么测,再考虑怎么开发 满足软件测试的可控范围 2、…...

vue3修改带小数点的价格数字:小数点的前后数字,要分别显示成不同颜色和大小!已经封装成组件了!
需求: 修改带小数点的价格数字:小数点的前后数字,要分别显示成不同颜色和大小!已经封装成组件了! 效果: 前面大,后面小 代码: 组件: <!--修改小数点前后数字不同…...
JVM(Java虚拟机) - JVM内存分配与内存管理
作者:逍遥Sean 简介:一个主修Java的Web网站\游戏服务器后端开发者 主页:https://blog.csdn.net/Ureliable 觉得博主文章不错的话,可以三连支持一下~ 如有疑问和建议,请私信或评论留言! 前言 Java虚拟机&…...

Linux中vim的基本介绍和使用
善为理者,举其纲,疏其网。 vim 1、vim介绍2、命令模式详情3、底行模式详情4、困难问题5、历史存疑问题6、vim配置问题6、1、配置的原理6、2、一键式配置 1、vim介绍 如果我面想要在Linux上编写代码的话,我就需要vim来帮助我们编写代码。但是…...

宝塔面板上,安装rabbitmq
废话不多说,直接上干货! 第一步:登录宝塔账号,在软件商店里搜索 第二步:点击设置 第三步:已经完成了,还看啥!...

【Docker系列】Docker 镜像管理:删除无标签镜像的技巧
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...

自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...