专栏首页爱编码经典算法之广度&深度搜索

经典算法之广度&深度搜索

广度优先搜索

广度优先搜索算法(Breadth First Search),又称为"宽度优先搜索"或"横向优先搜索",简称BFS。

它的思想是:从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。

换句话说,广度优先搜索遍历图的过程是以v为起点,由近至远,依次访问和v有路径相通且路径长度为1,2…的顶点。

无向图的广度优先搜索

下面以"无向图"为例,来对广度优先搜索进行演示。还是以上面的图G1为例进行说明。

第1步:访问A。 第2步:依次访问C,D,F。 在访问了A之后,接下来访问A的邻接点。前面已经说过,在本文实现中,顶点ABCDEFG按照顺序存储的,C在"D和F"的前面,因此,先访问C。再访问完C之后,再依次访问D,F。 第3步:依次访问B,G。 在第2步访问完C,D,F之后,再依次访问它们的邻接点。首先访问C的邻接点B,再访问F的邻接点G。 第4步:访问E。 在第3步访问完B,G之后,再依次访问它们的邻接点。只有G有邻接点E,因此访问G的邻接点E。

因此访问顺序是:A -> C -> D -> F -> B -> G -> E

有向图的广度优先搜索

类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点。

具体算法表述如下:

第1步:访问初始结点v并标记结点v为已访问。

第2步:结点v入队列

第3步:当队列非空时,继续执行,否则算法结束。

第4步:出队列,取得队头结点u。

第5步:查找结点u的第一个邻接结点w。

第6步:若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤: 1). 若结点w尚未被访问,则访问结点w并标记为已访问。 2). 结点w入队列 3). 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。

如下图,其广度优先算法的遍历顺序为:1->2->3->4->5->6->7->8

深度优先搜索

深度优先遍历,从初始访问结点出发,我们知道初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点。总结起来可以这样说:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

无向图的深度优先搜索

下面以"无向图"为例,来对深度优先搜索进行演示。

对上面的图G1进行深度优先遍历,从顶点A开始。

第1步:访问A。 第2步:访问(A的邻接点)C。 在第1步访问A之后,接下来应该访问的是A的邻接点,即"C,D,F"中的一个。但在本文的实现中,顶点ABCDEFG是按照顺序存储,C在"D和F"的前面,因此,先访问C。 第3步:访问(C的邻接点)B。 在第2步访问C之后,接下来应该访问C的邻接点,即"B和D"中一个(A已经被访问过,就不算在内)。而由于B在D之前,先访问B。 第4步:访问(C的邻接点)D。 在第3步访问了C的邻接点B之后,B没有未被访问的邻接点;因此,返回到访问C的另一个邻接点D。 第5步:访问(A的邻接点)F。 前面已经访问了A,并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)";因此,此时返回到访问A的另一个邻接点F。 第6步:访问(F的邻接点)G。 第7步:访问(G的邻接点)E。

因此访问顺序是:A -> C -> B -> D -> F -> G -> E

有向图的深度优先搜索

我们从这里可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。

具体算法表述如下:

第1步:访问初始结点v,并标记结点v为已访问。

第2步:查找结点v的第一个邻接结点w。

第3步:若w存在,则继续执行4,否则算法结束。

第4步:若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。

第5步:查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

例如下图,其深度优先遍历顺序为 1->2->4->8->5->3->6->7

Java源码

源码地址:https://dwz.cn/isCTEE0n 3.1 邻接矩阵实现的无向图(MatrixUDG.java) 3.2 邻接表实现的无向图(ListUDG.java) 3.3 邻接矩阵实现的有向图(MatrixDG.java) 3.4 邻接表实现的有向图(ListDG.java)

本文分享自微信公众号 - 爱编码(ilovecode)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 闭包还可以这样写?谈谈少儿编程工具的实现思路

      看看这段代码,很明显,是列举出100以内所有的质数。类似这样的程序我们从学程序开始写过很多。

    窗户
  • fio与iometer

       FIO是测试IOPS的非常好的工具,用来对硬件进行压力测试和验证,支持13种不同的I/O引擎,包括:sync,mmap, libaio, posixaio...

    孙杰
  • 分析 JDK 源码丨Java HashMap

    HashMap 是数组和链表组合组成的复杂结构,哈希值决定了键值在数组的位置,当哈希值相同时则以链表形式存储,当链表长度到达设定的阈值则会对其进行树化,这样做是...

    码脑
  • 学习Spring的思考框架

    很早之前听同事说:“要开会了。我都知道领导要问什么,就那几板斧。”其实领导之所以为领导,人家问的问题确实很合情合理,甚至可以说一针见血。而之所以能问出来这些合理...

    静儿
  • C语言——小学二年级题目解析(一)

    程序填空题开始,到阅读理解题,到编程题,首先要有自己的思路,而且思路要清晰,想清楚再动手写,事半功倍。具体心得,等清完1-4年级题目会来一篇。

    Ed_Frey
  • 网卡绑定导致 ESXi 中的虚机网络连接时断时续的解析和处理

    当你使用以太通道进行网卡绑定时,ESXi 主机中的虚机网络连接有时会出现时断时续现象。之所以出现此问题,是因为网卡绑定属性没有传播到 ESXi 中的管理网络端口...

    孙杰
  • ESXi 主机失去与 ESXi 和 VMFS5 数据存储的连接

       在虚拟化环境中使用 VAAI ATS 检测信号时,ESXi 5.5 Update 2 或 ESXi 6.0 主机失去与 VMFS5 数据存储的连接,会造成...

    孙杰
  • C语言——小学一年级题目解析(三)

    另外有一个'\0'需要重点记忆,它是字符串结束的标志位。但是在这个字符串数组里,它是啥??我也不懂

    Ed_Frey
  • Zookeeper 配置详解

    Zookeeper是通过一个***.cfg配置文件来进行配置管理的,默认使用zoo.cfg文件进行配置。下面我们将仔细介绍Zookeeper的配置项及该配置项的...

    用户5760343
  • windows2012的NIC Teaming配置

      NIC 成组也称为负载平衡和故障转移 (LBFO),它允许出于以下目的将一台计算机上的多个网络适配器放置到一个小组中:

    孙杰

扫码关注云+社区

领取腾讯云代金券