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

【算法】浅析深度优先搜索算法

深度优先搜索算法:深入探索,穷尽可能

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. 深度优先搜索算法的意义

  1. 探索所有可能:DFS能够探索所有可能的路径,这对于解决某些类型的问题(如迷宫问题、棋盘游戏等)非常有用。
  2. 检测连通性:在图论中,DFS可以用来检测图的连通性,包括找出所有的连通分量。
  3. 简化问题:通过递归的方式,DFS可以将复杂的问题简化为更小的子问题,使得问题更容易处理。
  4. 高效的空间利用: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框&#xf…...

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修改带小数点的价格数字:小数点的前后数字,要分别显示成不同颜色和大小!已经封装成组件了!

需求&#xff1a; 修改带小数点的价格数字&#xff1a;小数点的前后数字&#xff0c;要分别显示成不同颜色和大小&#xff01;已经封装成组件了&#xff01; 效果&#xff1a; 前面大&#xff0c;后面小 代码&#xff1a; 组件&#xff1a; <!--修改小数点前后数字不同…...

JVM(Java虚拟机) - JVM内存分配与内存管理

作者&#xff1a;逍遥Sean 简介&#xff1a;一个主修Java的Web网站\游戏服务器后端开发者 主页&#xff1a;https://blog.csdn.net/Ureliable 觉得博主文章不错的话&#xff0c;可以三连支持一下~ 如有疑问和建议&#xff0c;请私信或评论留言&#xff01; 前言 Java虚拟机&…...

Linux中vim的基本介绍和使用

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

宝塔面板上,安装rabbitmq

废话不多说&#xff0c;直接上干货&#xff01; 第一步&#xff1a;登录宝塔账号&#xff0c;在软件商店里搜索 第二步&#xff1a;点击设置 第三步&#xff1a;已经完成了&#xff0c;还看啥&#xff01;...

【Docker系列】Docker 镜像管理:删除无标签镜像的技巧

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...