算法总结-深度优先遍历和广度优先遍历
深度优先遍历(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,简称DFS) 与广度优先遍历(Breath First Search,简称BFS)是图论中两种非常重要的算法,生产上广泛用于拓扑排序,寻路(走迷宫),搜索引擎,爬虫等。 一、深度优先遍历 深度优先…...
【Linux】Centos安装mvn命令(maven)
🍁博主简介 🏅云计算领域优质创作者 🏅华为云开发者社区专家博主 🏅阿里云开发者社区专家博主 💊交流社区:运维交流社区 欢迎大家的加入! 文章目录一、下载maven包方法一:官…...
驱动保护 -- 通过PID保护指定进程
一、设计界面 1、添加一个编辑框输入要保护的进程PID,并添加两个按钮,一个保护进程,一个解除保护 2、右击编辑框,添加变量 二、驱动层代码实现 1、声明一个受保护的进程PID数组 static UINT32 受保护的进程PID[256] { 0 }; 2…...
spring常用注解(全)
一、前言 Spring的一个核心功能是IOC,就是将Bean初始化加载到容器中,Bean是如何加载到容器的,可以使用Spring注解方式或者Spring XML配置方式。 Spring注解方式减少了配置文件内容,更加便于管理,并且使用注解可以大大…...
Axios请求(对于ajax的二次封装)——Axios请求的响应结构、默认配置
Axios请求(对于ajax的二次封装)——Axios请求的响应结构、默认配置知识回调(不懂就看这儿!)场景复现核心干货axios请求的响应结构响应格式详解实际请求中的响应格式axios请求的默认配置全局axios默认值(了解…...
(三)【软件设计师】计算机系统—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
一、配置好的环境: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版本有点低,但是折腾不如先配上用了,以后有需要再说。 (后话:py 3.9 pytorch 1.12.1 cuda …...
JS字符串对象
、 JS字符串对象 1.1 内置对象简介 在 JavaScript 中,对象是非常重要的知识点。对象可以分为两种:一种是“自定义对象”外一种是“内置对象”。自定义对象,指的是需要我们自己定义的对象,和“自定义函数”是一些道理;内置对象,…...
Linux系统对文件及目录的权限管理(chmod、chown)
1、身份介绍 在linux系统中,对文件或目录来说访问者的身份有三种: ①、属主用户,拥有者(owner)文件的创建者 ②、属组用户,和文件的owner同组的用户(group); ③、其他用…...
半透明反向代理 (基于策略路由)
定义 半透明反向代理一般是指 代理本身对于客户端透明,对于服务端可见。 从客户端视角看,客户端访问的还是服务端,客户端不知道代理的存在。 从服务端视角看,服务端只能看到代理,看不到真实的客户端。 示意图 客户端…...
课前测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题就是一个简单的进制转化,代码实现如下: #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,主要支持两种搜索方法: Config mode:查找 xxx-config.cmake或 xxxConfig.cmake的文件,如OpenCV库的OpenCVConfig.cmakeModule mode:查找Findxxx.cmake文件,如Ope…...
WEB攻防-通用漏洞PHP反序列化POP链构造魔术方法原生类
目录 一、序列化和反序列化 二、为什么会出现反序列化漏洞 三、序列化和反序列化演示 <演示一> <演示二> <演示二> 四、漏洞出现演示 <演示一> <演示二> 四、ctfshow靶场真题实操 <真题一> <真题二> <真题三> &l…...
Baumer工业相机堡盟工业相机如何通过BGAPISDK里的图像处理库进行图像转换(C++)
Baumer工业相机堡盟工业相机如何通过BGAPI SDK进行图像转换(C)Baumer工业相机Baumer工业相机的SDK里图像格式转换的技术背景Baumer工业相机通过BGAPI SDK进行图像转换调用BGAPI SDK的图像转换库ImageProcessor调用BGAPI SDK建立图像调用BGAPI SDK转换图像…...
JD开放平台接口(获得JD商品详情, 按关键字搜索商品,按图搜索京东商品(拍立淘), 获得店铺的所有商品,获取推荐商品列表, 获取购买到的商品订单列表)
参数说明 通用参数说明 url说明 https://api-gw.onebound.cn/平台/API类型/ 平台:淘宝,京东等, API类型:[item_search,item_get,item_search_shop等]version:API版本key:调用key,测试key:test_api_keysecret:调用secret,测试secret:(不用填写…...
上海亚商投顾:沪指震荡反弹 游戏、传媒概念股再度大涨
上海亚商投顾前言:无惧大盘涨跌,解密龙虎榜资金,跟踪一线游资和机构资金动向,识别短期热点和强势个股。 市场情绪大小指数今日走势分化,沪指向上震荡反弹,创业板指一度跌近1%,黄白二线大幅背离。…...
C/C++ 玩转StoneValley库:从入门到精通
C/C 玩转StoneValley库:从入门到精通引言(Introduction)StoneValley库简介(Overview of StoneValley Library)为什么要学习StoneValley库(Why Learn StoneValley Library in C)StoneValley库安装…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
