图的深度遍历和广度遍历

理论部分

图的深度遍历和广度遍历都不算很难像极了二叉树的前序遍历和层序遍历,如下面的图,可以用右边的邻接矩阵进行表示,假设以顶点0开始对整幅图进行遍历的话,两种遍历方式的思想如下:

1. 深度优先遍历(depthFirstSearch—DFS)

由初始顶点开始,沿着一条道一直走,当走到走不动的时候,再回来走一条可以走的通的道,然后再继续往下走,直到走不动,再回来…对应于本图来说就是从0开始往前走,到1----->然后从1再往前走,到5----->从5再往前走,到4------->到了这里发现没路可走了------>就往回走,回到5,看5还有没有路,发现没路----->则回到1,看1有没有路,也没有----->再回到0,看0有没有路,发现有------>则由0走到3----->走到这里发现又没有路了----->再往回走,走到0,看0还有没有路,发现有----->则由0走到4,但是4已经被遍历过了,所以再回到0,结束这次遍历过程

但是这时候还有一个2没有遍历啊,该怎么办呢?之前我们是直接就默认从0开始进行往下遍历了,但是从0开始遍历没有一条路可以走到2,为了避免这种情况,我们必须得从每一个顶点开始遍历,这样才能避免漏掉这种只出不进的顶点

于是深度优先遍历得到的遍历结果应为:0 1 5 4 3 2

2.广度优先遍历(broadFirstSearch—BFS)

广度遍历我觉得理解起来更简单,就是一层一层的进行遍历,比如说以0顶点开始,0往下指向1,3,4,遍历的时候就先遍历0,然后再遍历它下一层的1,3,4------>然后分别遍历1,3,4的下一层---->而1,3,4只有1有下一层,则遍历1的下一层5,同理最后遍历2

即广度优先遍历得到的遍历结果应为:0 1 3 4 5 2

和二叉树的层序遍历一样,图的广度遍历也用到了队列,对于下图而言,先将0放入队首----->然后遍历0并将0从队列中取出,同时将0的邻接点1,3,4入队,这样队首就是1----->然后将1出队,并将1的邻接点入队(这里只有5), 这样队首就是3----->然后将3弹出并将3的邻接点入队(这里没有),这样队首就是4----->然后将4弹出并将4的邻接点入队(这里没有),队首就是从1入队的1的第一个邻接点(这里是5)---->然后将5弹出----->直到队列为空这样就完成了由定点0开始的广度优先遍历

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏完美Excel

VBA实用小程序60: 替换图表SERIES公式中的字符串

大家知道,Excel图表的每个系列使用的数据都是由SERIES公式来确定的。当我们选取图表中的某个数据系列时,在公式栏中就会显示相应的SERIES公式,但这个公...

9520
来自专栏码神路漫漫

如何实现 Go Module 依赖关系的可视化

最近,我开发了一个非常简单的小工具,总的代码量 200 行不到。今天,简单介绍下它。这是个什么工具呢?它是一个用于可视化展示 Go Module 依赖关系的工具...

13410
来自专栏机器之心

获顶会最佳论文,天津大学等用强化学习寻找游戏bug

软件工程领域顶级会议 34th IEEE/ACM International Conference on Automated Software Engineer...

18010
来自专栏Crossin的编程教室

【Python 第75课】可迭代对象和迭代器

for 循环是我们在 Python 里非常常用的一个语法,但你有没有思考过 for 循环是怎样实现的?

10520
来自专栏全栈前端精选

Redis 到底是怎么实现“附近的人”这个功能的呢?

针对“附近的人”这一位置服务领域的应用场景,常见的可使用PG、MySQL和MongoDB等多种DB的空间索引进行实现。而Redis另辟蹊径,结合其有序队列zse...

10910
来自专栏前端自习课

【JS】388- 深入了解强大的 ES6 「 ... 」 运算符

... 运算符,是 ES6 里一个新引入的运算法,也叫 展开/收集 运算符,我们每天都要和它打交道。

8020
来自专栏理想二旬不止

数据结构【第五篇】栈 (stack) 的实现与讲解

① 举一个生活中的例子:我在一个储物箱中,堆了一堆衣服,我的一件球衣在最下面,而我要拿这件衣服,就意味着我必须将上面的衣服全部拿出来才可以,但是由于箱子只有一个...

12330
来自专栏Java技术栈

如何写出让同事好维护的代码?

写出整洁的代码,是每个程序员的追求。《clean code》指出,要想写出好的代码,首先得知道什么是肮脏代码、什么是整洁代码;然后通过大量的刻意练习,才能真正写...

11720
来自专栏芋道源码1024

一个 Java 对象到底有多大?

编写Java代码的时候,大多数情况下,我们很少关注一个Java对象究竟有多大(占据多少内存),更多的是关注业务与逻辑。但是殊不知,在我们不经意间,大量的内存被无...

10510
来自专栏业余草

面试再问ThreadLocal,别说你不会

以前面试的时候问到ThreadLocal总是一脸懵逼,只知道有这个哥们,不了解他是用来做什么的,更不清楚他的原理了。表面上看他是和多线程,线程同步有关的一个工具...

6910

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励