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

算法总结-深度优先遍历和广度优先遍历

深度优先遍历(Depth First Search,简称DFS) 与广度优先遍历(Breath First Search,简称BFS)是图论中两种非常重要的算法,生产上广泛用于拓扑排序,寻路(走迷宫),搜索引擎,爬虫等。

一、深度优先遍历
深度优先遍历的思路是从图的一个未访问的顶点V开始,沿着一条路一直走到底,然后从这条路尽头的节点回退到上一个节点,再从另一条路开始走到底,不断递归重复此过程…直到所有的顶点都遍历完成。它的特点说通俗了就是不撞南墙不回头,走完了一条路,再换一条路继续走。
树是图的一种特例( 联通无环的图就是树),接下来我们来看树用深度优先遍历该怎么遍历。
1、深度优先遍历过程
在这里插入图片描述
(1)、我们从根节点1开始深度优先遍历,它相邻的节点有2、3、4,依先遍历节点2,再遍历2的右边节点5,再遍历9,至此便无可遍历的节点。
在这里插入图片描述

(2)、上图中一条路径已经遍历到底,此时从叶子节点9回退到上一节点5,,看下节点 5 是否还有除 9 以外的节点,没有继续回退到 2,2 也没有除 5 以外的节点,回退到 1,1 有除 2 以外的节点 3,所以从节点 3 开始进行深度优先遍历,如下:
在这里插入图片描述
(3)、同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点,再往上回溯,发现3有除 6 以外的子节点 7,所以此时会遍历 7。
在这里插入图片描述
(4)、从 7 往上回溯到 3, 1,发现 1 还有节点 4 未遍历,所以此时沿着 4, 8 进行遍历,这样就完成了整个遍历过程。
完整的节点的遍历顺序如下(节点上的的蓝色数字代表):
在这里插入图片描述
相信大家看到以上的遍历不难发现这就是树的前序遍历,实际上不管是前序遍历,还是中序遍历,亦或是后序遍历,都属于深度优先遍历。

那么深度优先遍历该怎么实现呢,有递归和非递归两种表现形式,接下来我们以二叉树为例来看下如何分别用递归和非递归来实现深度优先遍历。
2、深度优先遍历实现
(1)、递归
递归实现比较简单,由于是前序遍历,所以我们依次遍历当前节点,左节点,右节点即可,对于左右节点来说,依次遍历它们的左右节点即可,依此不断递归下去,直到叶节点(递归终止条件),代码如下:

public class Solution { private static class Node { public int value;  // 节点值public Node left;  // 左节点  public Node right;  // 右节点public Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; } } public static void dfs(Node treeNode) { if (treeNode == null) { return; } process(treeNode);  // 遍历节点dfs(treeNode.left);  // 遍历左节点dfs(treeNode.right);  // 遍历右节点} 
} 

递归的表达性很好,也很容易理解,不过如果层级过深,很容易导致栈溢出。所以我们重点看下非递归实现。
(2)、非递归
仔细观察深度优先遍历的特点,对二叉树来说,由于是先序遍历(先遍历当前节点,再遍历左节点,再遍历右节点),所以我们有如下思路:

对于每个节点来说,先遍历当前节点,然后把右节点压栈,再压左节点(这样弹栈的时候会先拿到左节点遍历,符合深度优先遍历要求)。
弹栈,拿到栈顶的节点,如果节点不为空,重复步骤 1, 如果为空,结束遍历。
我们以以下二叉树为例来看下如何用栈来实现 DFS。
在这里插入图片描述
在这里插入图片描述

使用栈来将要遍历的节点压栈,然后出栈后检查此节点是否还有未遍历的节点,有的话压栈,没有的话不断回溯(出栈),有了思路,不难写出如下用栈实现的二叉树的深度优先遍历代码:

/** * 使用栈来实现 dfs * @param root */ 
public static void dfsWithStack(Node root) { if (root == null) { return; } Stack<Node> stack = new Stack<>(); // 先把根节点压栈 stack.push(root); while (!stack.isEmpty()) { Node treeNode = stack.pop(); // 遍历节点 process(treeNode) // 先压右节点 if (treeNode.right != null) { stack.push(treeNode.right); } // 再压左节点 if (treeNode.left != null) { stack.push(treeNode.left); } } 
}

二、深度优先遍历
广度优先遍历,指的是从图的一个未遍历的节点出发,先遍历这个节点的相邻节点,再依次遍历每个相邻节点的相邻节点。

上面所述树的广度优先遍历动图如下,每个节点的值即为它们的遍历顺序。所以广度优先遍历也叫层序遍历,先遍历第一层(节点 1),再遍历第二层(节点 2,3,4),第三层(5,6,7,8),第四层(9,10)。
在这里插入图片描述

深度优先遍历用的是栈,而广度优先遍历要用队列来实现,我们以下图二叉树为例来看看如何用队列来实现广度优先遍历。
在这里插入图片描述
在这里插入图片描述
代码实现如下:

/** * 使用队列实现 bfs * @param root */ 
private static void bfs(Node root) { if (root == null) { return; } Queue<Node> stack = new LinkedList<>(); stack.add(root); while (!stack.isEmpty()) { Node node = stack.poll(); System.out.println("value = " + node.value); Node left = node.left; if (left != null) { stack.add(left); } Node right = node.right; if (right != null) { stack.add(right); } } 
} 

若想通过实战来进一步理解DFS,BFS,可以看LeetCode如下题目,这是一道典型的DFS,BFS题目。
leetcode 104,111: 给定一个二叉树,找出其最大/最小深度。

相关文章:

算法总结-深度优先遍历和广度优先遍历

深度优先遍历(Depth First Search&#xff0c;简称DFS) 与广度优先遍历(Breath First Search&#xff0c;简称BFS)是图论中两种非常重要的算法&#xff0c;生产上广泛用于拓扑排序&#xff0c;寻路(走迷宫)&#xff0c;搜索引擎&#xff0c;爬虫等。 一、深度优先遍历 深度优先…...

【Linux】Centos安装mvn命令(maven)

&#x1f341;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; 文章目录一、下载maven包方法一&#xff1a;官…...

驱动保护 -- 通过PID保护指定进程

一、设计界面 1、添加一个编辑框输入要保护的进程PID&#xff0c;并添加两个按钮&#xff0c;一个保护进程&#xff0c;一个解除保护 2、右击编辑框&#xff0c;添加变量 二、驱动层代码实现 1、声明一个受保护的进程PID数组 static UINT32 受保护的进程PID[256] { 0 }; 2…...

spring常用注解(全)

一、前言 Spring的一个核心功能是IOC&#xff0c;就是将Bean初始化加载到容器中&#xff0c;Bean是如何加载到容器的&#xff0c;可以使用Spring注解方式或者Spring XML配置方式。 Spring注解方式减少了配置文件内容&#xff0c;更加便于管理&#xff0c;并且使用注解可以大大…...

Axios请求(对于ajax的二次封装)——Axios请求的响应结构、默认配置

Axios请求&#xff08;对于ajax的二次封装&#xff09;——Axios请求的响应结构、默认配置知识回调&#xff08;不懂就看这儿&#xff01;&#xff09;场景复现核心干货axios请求的响应结构响应格式详解实际请求中的响应格式axios请求的默认配置全局axios默认值&#xff08;了解…...

(三)【软件设计师】计算机系统—CPU习题联系

文章目录一、2014年上半年第1题二、2014年下半年第3题三、2017年上半年第1题四、2009年下半年第1题五、2010年上半年第5题六、2011年下半年第5题七、2011年下半年第6题八、2012年下半年第1题九、2019年上半年第1题十、2010年上半年第1题十一、2011年上半年第1题十二、2016年下半…...

win下配置pytorch3d

一、配置好的环境&#xff1a;py 3.9 pytorch 1.8.0 cuda 11.1_cudnn 8_0 pytorch3d 0.6.0 CUB 1.11.0 你可能觉得pytorch3d 0.6.0版本有点低&#xff0c;但是折腾不如先配上用了&#xff0c;以后有需要再说。 &#xff08;后话&#xff1a;py 3.9 pytorch 1.12.1 cuda …...

JS字符串对象

、 JS字符串对象 1.1 内置对象简介 在 JavaScript 中&#xff0c;对象是非常重要的知识点。对象可以分为两种:一种是“自定义对象”外一种是“内置对象”。自定义对象&#xff0c;指的是需要我们自己定义的对象&#xff0c;和“自定义函数”是一些道理;内置对象&#xff0c;…...

Linux系统对文件及目录的权限管理(chmod、chown)

1、身份介绍 在linux系统中&#xff0c;对文件或目录来说访问者的身份有三种&#xff1a; ①、属主用户&#xff0c;拥有者&#xff08;owner&#xff09;文件的创建者 ②、属组用户&#xff0c;和文件的owner同组的用户&#xff08;group&#xff09;&#xff1b; ③、其他用…...

半透明反向代理 (基于策略路由)

定义 半透明反向代理一般是指 代理本身对于客户端透明&#xff0c;对于服务端可见。 从客户端视角看&#xff0c;客户端访问的还是服务端&#xff0c;客户端不知道代理的存在。 从服务端视角看&#xff0c;服务端只能看到代理&#xff0c;看不到真实的客户端。 示意图 客户端…...

课前测5-超级密码

目录 课前测5-超级密码 程序设计 程序分析 课前测5-超级密码 【问题描述】 上次设计的“高级密码”被你们破解了,一丁小朋友很不服气! 现在,他又设计了一套更加复杂的密码,称之为“超级密码”。 说实话,这套所谓的“超级密码”其实也并不难: 对于一个给定的字符…...

QML控件--Menu

文章目录一、控件基本信息二、控件使用三、属性成员四、成员函数一、控件基本信息 二、控件使用 import QtQuick 2.10 import QtQuick.Window 2.10 import QtQuick.Controls 2.3ApplicationWindow{visible: true;width: 1280;height: 720;Button {id: fileButtontext: "Fi…...

002:Mapbox GL更改大气、空间及星星状态

第002个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中更改大气、空间及星星状态 。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共71行)相关API参考:专栏目标示例效果 配置方式 1)查看基础设置:…...

2022年第十三届蓝桥杯题解(全)C/C++

A题就是一个简单的进制转化&#xff0c;代码实现如下&#xff1a; #include <bits/stdc.h>using namespace std;const int N 1e5 10;int main() {int x 2022;int a 1;int res 0;while(x) {res (x % 10) * a;a a * 9;x / 10;}cout << res;return 0; } B题有…...

【cmake学习】find_package 详解

find_package 主要用于查找指定的 package&#xff0c;主要支持两种搜索方法&#xff1a; Config mode&#xff1a;查找 xxx-config.cmake或 xxxConfig.cmake的文件&#xff0c;如OpenCV库的OpenCVConfig.cmakeModule mode&#xff1a;查找Findxxx.cmake文件&#xff0c;如Ope…...

WEB攻防-通用漏洞PHP反序列化POP链构造魔术方法原生类

目录 一、序列化和反序列化 二、为什么会出现反序列化漏洞 三、序列化和反序列化演示 <演示一> <演示二> <演示二> 四、漏洞出现演示 <演示一> <演示二> 四、ctfshow靶场真题实操 <真题一> <真题二> <真题三> &l…...

Baumer工业相机堡盟工业相机如何通过BGAPISDK里的图像处理库进行图像转换(C++)

Baumer工业相机堡盟工业相机如何通过BGAPI SDK进行图像转换&#xff08;C&#xff09;Baumer工业相机Baumer工业相机的SDK里图像格式转换的技术背景Baumer工业相机通过BGAPI SDK进行图像转换调用BGAPI SDK的图像转换库ImageProcessor调用BGAPI SDK建立图像调用BGAPI SDK转换图像…...

JD开放平台接口(获得JD商品详情, 按关键字搜索商品,按图搜索京东商品(拍立淘), 获得店铺的所有商品,获取推荐商品列表, 获取购买到的商品订单列表)

参数说明 通用参数说明 url说明 https://api-gw.onebound.cn/平台/API类型/ 平台&#xff1a;淘宝&#xff0c;京东等&#xff0c; API类型:[item_search,item_get,item_search_shop等]version:API版本key:调用key,测试key:test_api_keysecret:调用secret,测试secret:(不用填写…...

上海亚商投顾:沪指震荡反弹 游戏、传媒概念股再度大涨

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 市场情绪大小指数今日走势分化&#xff0c;沪指向上震荡反弹&#xff0c;创业板指一度跌近1%&#xff0c;黄白二线大幅背离。…...

C/C++ 玩转StoneValley库:从入门到精通

C/C 玩转StoneValley库&#xff1a;从入门到精通引言&#xff08;Introduction&#xff09;StoneValley库简介&#xff08;Overview of StoneValley Library&#xff09;为什么要学习StoneValley库&#xff08;Why Learn StoneValley Library in C&#xff09;StoneValley库安装…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

技术栈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 主题模式…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...