深度优先和广度优先算法

待我称王封你为后i 2023-09-30 10:22 10阅读 0赞

![9ab6037a79e8dbf95ba7c443c284a0e1.png][]

### 1、深度优先算法 ###

**遍历规则**：不断地沿着顶点的深度方向遍历。顶点的深度方向是指它的邻接点方向。

**最后得出的结果为：**ABDECFHG。

Python代码实现的伪代码如下：

![283448eaa608423b0bb58b9eba1a88dc.png][]

### 2、广度优先算法： ###

**遍历规则：**

1）先访问完当前顶点的所有邻接点。(应该看得出广度的意思)

2）先访问顶点的邻接点先于后访问顶点的邻接点被访问。

**最后得出的结果为**：ABCDEFGH。

**Python代码实现的伪代码如下：**

![3d8c99805f85eae2afa3a10f72647862.png][]

### 3.总结 ###

深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历（我们前面使用的是先序遍历）。具体说明如下：

先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。

后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止

#### 4、分析 ####

深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。

广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。

通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。

所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。

广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。

但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些

[9ab6037a79e8dbf95ba7c443c284a0e1.png]: https://img-blog.csdnimg.cn/img_convert/9ab6037a79e8dbf95ba7c443c284a0e1.png
[283448eaa608423b0bb58b9eba1a88dc.png]: https://img-blog.csdnimg.cn/img_convert/283448eaa608423b0bb58b9eba1a88dc.png
[3d8c99805f85eae2afa3a10f72647862.png]: https://img-blog.csdnimg.cn/img_convert/3d8c99805f85eae2afa3a10f72647862.png

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关图算法实现：深度优先搜索和广度优先搜索

深度优先搜索（Depth-First Search）和广度优先搜索（Breadth-First Search）是图算法中常用的两种搜索方法。在本文中，我们将使用C++编程语言和

ゞ浴缸里的玫瑰/ 2023年10月16日 10:35/ 0 赞/ 71 阅读

相关深度优先和广度优先算法

![9ab6037a79e8dbf95ba7c443c284a0e1.png][] 1、深度优先算法遍历规则：不断地沿着顶点的深度方向遍历。顶点的深度方向是指它的邻接

待我称王封你为后i/ 2023年09月30日 10:22/ 0 赞/ 11 阅读

相关求二叉树深度算法（深度优先、广度优先）

求二叉树深度的算法求二叉树深度方法一：深度优先的遍历方式方法二：广度优先的遍历方式总结求二叉树深度注：本文中二叉

本是古典何须时尚/ 2022年12月27日 14:21/ 0 赞/ 189 阅读

相关 Python 树的深度优先和广度优先

""" 广度优先和深度优先 """ 树的节点，如果是第一个，则为root节点 class Node: def __init_

落日映苍穹つ/ 2022年12月05日 05:15/ 0 赞/ 170 阅读

相关基本图算法（广度优先搜索和深度优先搜索）

图算法对于计算机学科至关重要。成百上千的计算问题最后都可以归约为图论问题。本文主要是对《算法导论》图算法的学习笔记进行整理。首先，我们先对图算法中的一些表达方式进行统一：给

痛定思痛。/ 2022年08月25日 02:20/ 0 赞/ 272 阅读

相关图的深度优先和广度优先搜索算法

图的深度优先和广度优先搜索算法本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。本博文作为学习资料整理。附书的截图： ![Ce

清疚/ 2022年08月21日 03:22/ 0 赞/ 239 阅读

相关搜索算法之深度优先搜索和广度优先搜索

所谓深度优先搜索：就是一条道走到黑，不碰南墙不回头的那种。广度优先搜索：就是从你所站的位置向周围扩散性的搜索，通俗来讲，就是你在黑夜里眼睛掉了，你肯定是趴在地

梦里梦外;/ 2022年06月01日 06:36/ 0 赞/ 477 阅读

相关深度优先和广度优先搜索

目录前言 1 深度优先搜索 2 广度优先搜索 3 深度优先和广度优先的比较 -------------------- 前言最近面试，被问到了深度优先和广度

冷不防/ 2022年05月22日 13:39/ 0 赞/ 312 阅读

相关 BFS（广度优先搜索算法）和DFS（深度优先搜索算法）

注意：①BFS和DFS都是对图的遍历(按照某种次序访问图的每一顶点一次仅且一次) ②存储图的两种方式：邻接表和邻接矩阵（本质就是二维数组）一

港控/mmm°/ 2022年05月18日 08:16/ 0 赞/ 349 阅读

相关树的深度优先和广度优先

1.深度优先算法----采用栈(非递归) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aH

叁歲伎倆/ 2021年09月21日 00:56/ 0 赞/ 362 阅读