深度优先遍历和广度优先遍历分别是什么?

2021-02-26 14:52发布

3条回答
靓猴一枚
2楼 · 2021-02-28 11:37

深度优先遍历

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。

说白了深度优先遍历就是一种不撞南墙不会头的算法,他会把一条路走完之后再回溯到有分叉的节点继续遍历。
如图:

首先标记点0,然后按字典序寻找未标记的相邻点进行遍历(点1)。

标记点1,按字典序寻找未标记的相邻点继续遍历(点4)。

同步骤2,直到遍历到点3,因为与他相邻的点(点0,点6)都被标记过,所以回溯到点6,继续寻找点6的未标记的相邻点继续遍历(点7)。

标记点7,同步骤3,回溯点6。

这时点6的所有相邻点都被标记,回溯点4。

同步骤5,继续回溯到点1。

按字典序寻找点1的未标记的相邻点继续遍历(点2)。

同步骤2,遍历点5。

同步骤5,回溯到点0,此时整个图的点都被遍历过,结束。

遍历结果 01463725
例题:数据结构实验之图论二:图的深度遍历

广度优先遍历

从图中某个顶点V0出发,并访问此顶点;

从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点;

重复步骤2,直到全部顶点都被访问为止。
这是一种层层递进的算法,与树的层序遍历类似。
在广度优先搜索时,会从起点开始“一层一层”扩展的方法来遍历,扩展时每发现一个点就将这个点加入到队列,直到整张图都被遍历过位置。


希希
3楼 · 2021-03-02 08:40

深度优先遍历

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。

说白了深度优先遍历就是一种不撞南墙不会头的算法,他会把一条路走完之后再回溯到有分叉的节点继续遍历。
如图:

首先标记点0,然后按字典序寻找未标记的相邻点进行遍历(点1)。

标记点1,按字典序寻找未标记的相邻点继续遍历(点4)。

同步骤2,直到遍历到点3,因为与他相邻的点(点0,点6)都被标记过,所以回溯到点6,继续寻找点6的未标记的相邻点继续遍历(点7)。

标记点7,同步骤3,回溯点6。

这时点6的所有相邻点都被标记,回溯点4。

同步骤5,继续回溯到点1。

按字典序寻找点1的未标记的相邻点继续遍历(点2)。

同步骤2,遍历点5。

同步骤5,回溯到点0,此时整个图的点都被遍历过,结束。

遍历结果 01463725
例题:数据结构实验之图论二:图的深度遍历

广度优先遍历

从图中某个顶点V0出发,并访问此顶点;

从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点;

重复步骤2,直到全部顶点都被访问为止。
这是一种层层递进的算法,与树的层序遍历类似。
在广度优先搜索时,会从起点开始“一层一层”扩展的方法来遍历,扩展时每发现一个点就将这个点加入到队列,直到整张图都被遍历过位置。


寂静的枫林
4楼 · 2021-03-05 16:59

深度优先遍历

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。

说白了深度优先遍历就是一种不撞南墙不会头的算法,他会把一条路走完之后再回溯到有分叉的节点继续遍历。
如图:

首先标记点0,然后按字典序寻找未标记的相邻点进行遍历(点1)。

标记点1,按字典序寻找未标记的相邻点继续遍历(点4)。

同步骤2,直到遍历到点3,因为与他相邻的点(点0,点6)都被标记过,所以回溯到点6,继续寻找点6的未标记的相邻点继续遍历(点7)。

标记点7,同步骤3,回溯点6。

这时点6的所有相邻点都被标记,回溯点4。

同步骤5,继续回溯到点1。

按字典序寻找点1的未标记的相邻点继续遍历(点2)。

同步骤2,遍历点5。

同步骤5,回溯到点0,此时整个图的点都被遍历过,结束。

遍历结果 01463725
例题:数据结构实验之图论二:图的深度遍历

广度优先遍历

从图中某个顶点V0出发,并访问此顶点;

从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点;

重复步骤2,直到全部顶点都被访问为止。
这是一种层层递进的算法,与树的层序遍历类似。
在广度优先搜索时,会从起点开始“一层一层”扩展的方法来遍历,扩展时每发现一个点就将这个点加入到队列,直到整张图都被遍历过位置。


相关问题推荐

  • 回答 120

    相对前几年来说,要高上不少了,毕竟入行的人也是越来越多了,基础的工作对应想要参与的人群基数越来越大,但是对于高端人才的需求还是很多,人才还是相对稀缺性的。所以,想要学web或者其他技术也一样,别等,别观望。web前端就业方向特别多包括web前端开发...

  • 回答 25

    相对定位和绝对定位是定位的两种表现形式,区别如下:一、主体不同1、相对定位:是设置为相对定位的元素框会偏移某个距离。2、绝对定位:absolute 脱离文档流,通过 top,bottom,left,right 定位。二、特点不同1、相对定位:在使用相对定位时,无论是否进行移...

  • 抓包是什么意思?2020-04-01 17:36
    回答 7
    已采纳

    抓包(packet capture)就是将网络传输发送与接收的数据包进行截获、重发、编辑、转存等操作,也用来检查网络安全。抓包也经常被用来进行数据截取等。抓包可以通过抓包工具来查看网络数据包内容。通过对抓获的数据包进行分析,可以得到有用的信息。目前流行的...

  • 回答 89

    常用的前端框架有Bootstrap框架、React框架、Vue框架、Angular框架、Foundation框架等等

  • 回答 65
    已采纳

    前端是目的就业前景非常不错的一个计算机技术,但是自学的话还是有一定难度的,网络上自学是碎片化的,同时互联网技术跟新换代快,自己的话比较吃力也学习不到最新的技术。

  • SSR 是什么意思?2020-03-20 18:56
    回答 6

    SSR就是一台服务器,可以利用 SSR 在远程的服务器上配置 SSR,使其能够成为 SSR 节点,这样本地电脑或者其它设备利用 SSR 节点实现 VPN 或者远程上网及游戏加速等方面。ShadowsocksR(简称 SSR)是 Shadowsocks 分支,在 Shadowsocks 的基础上增加了一些数据...

  • 回答 11

    1、代码判断xAxis: {type: 'time',splitLine: {show: false},interval: 3600, // 设置x轴时间间隔axisLabel: {formatter: function(value, index) {return liangTools.unix2hm(value)}}},首先要把xAxis 显示类型设置成time,然后设置对应X轴......

  • 回答 52
    已采纳

    计算机培训方向比较多,建议找适合自己的方向选择培训编程类:JAVA、WEB、Python、C/C++、C#等测试类:软件测试运维类:云计算、网络安全设计类:UI设计、3D建模等

  • 回答 8

    HTML5 + CSS + JavaScript 开发 跨平台重用代码 

  • 回答 4

    采用rem单位自动响应,并提供独有栅格化系统快速定义宽高、边距节省css代码量,同时总结各大型移动端网页,提供一套ui颜色搭配规范,尺寸规范,字体规范等。

  • 回答 10

    iView UI、ioni、SUI

  • 回答 6

     jQTouch 

  • 回答 4

    如果只是普通的移动端用vue react 或者dva 如果是要编译成小程序什么的或者混生 就用uni-app(对应vue语法)taro(对应react) 或者纯原生 这个没有限制的,自己怎么舒服怎么来

  • 回答 4

    因为可以运用在网页和小程序的开饭中,而且开源,用着便宜,企业都很喜欢

  • 回答 10

    一、Visual Studio Code下载地址:https://code.visualstudio.com/微软在2015年4月30日Build 开发者大会上正式宣布了 Visual Studio Code 项目:一个运行于 Mac OS X、Windows和 Linux 之上的,针对于编写现代 Web 和云应用的跨平台源代码编辑器。Visual Stud...

  • 回答 9

    jQuery自带淡入淡出效果 https://www.w3school.com.cn/jquery/jquery_fade.asp 看看这个 

没有解决我的问题,去提问