首页
学习
活动
专区
工具
TVP
发布

图的搜索算法太难懂?算法图解带你轻松理解

前言

作者之前也看过很多算法数,对于图的这块算法一直觉得似懂非懂。这次看《算法图解》的时候才觉得豁然开朗。废话不多说,让我们开始学习:

广度优先搜索是一种用于图的查找算法,可帮助回答两类问题。

第一类问题:从节点A出发,有前往节点B的路径吗?

第二类问题:从节点A出发,前往节点B的哪条路径最短?

假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。

这种查找很简单。首先,创建一个朋友名单。

然后,依次检查名单中的每个人,看看他是否是芒果销售商。

假设你没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找。

检查名单中的每个人时,你都将其朋友加入名单。

这样一来,你不仅在朋友中查找,还在朋友的朋友中查找。别忘了,你的目标是在你的人际关系网中找到一位芒果销售商。因此,如果Alice不是芒果销售商,就将其朋友也加入到名单中。

这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网,直到找到芒果销售商。这就是广度优先搜索算法。

刚才你看到了如何回答第一类问题,下面来尝试回答第二类问题——谁是关系最近的芒果销

售商。例如,朋友是一度关系,朋友的朋友是二度关系。

在你看来,一度关系胜过二度关系,二度关系胜过三度关系,以此类推。因此,你应先在一度关系中搜索,确定其中没有芒果销售商后,才在二度关系中搜索。广度优先搜索就是这样做的!

在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系。顺便问一句:将先检查Claire还是Anuj呢?Claire是一度关系,而Anuj是二度关系,因此将先检查Claire,后检查Anuj。

你也可以这样看,一度关系在二度关系之前加入查找名单。

你按顺序依次检查名单中的每个人,看看他是否是芒果销售商。这将先在一度关系中查找,再在二度关系中查找,因此找到的是关系最近的芒果销售商。广度优先搜索不仅查找从A到B的路径,而且找到的是最短的路径。

注意,只有按添加顺序查找时,才能实现这样的目的。换句话说,如果Claire先于Anuj加入名单,就需要先检查Claire,再检查Anuj。如果Claire和Anuj都是芒果销售商,而你先检查Anuj再检查Claire,结果将如何呢?找到的芒果销售商并非是与你关系最近的,因为Anuj是你朋友的朋友,而Claire是你的朋友。因此,你需要按添加顺序进行检查。有一个可实现这种目的的数据结构,那就是队列(queue)。队列是一种先进先出(First In First Out,FIFO)的数据结构,而栈是一种后进先出(Last In First Out,LIFO)的数据结构。知道队列的工作原理后,我们来实现广度优先搜索!

实现图

首先,需要使用代码来实现图。图由多个节点组成。

每个节点都与邻近节点相连,如果表示类似于“你Bob”这样的关系呢?好在你知道的一种结构让你能够表示这种关系,它就是散列表!记住,散列表让你能够将键映射到值。在这里,你要将节点映射到其所有邻居。

表示这种映射关系的Python代码如下。

注意,“你”被映射到了一个数组,因此graph[“you”]是一个数组,其中包含了“你”的所有邻居。

图不过是一系列的节点和边,因此在Python中,只需使用上述代码就可表示一个图。那像下面这样更大的图呢?

表示它的Python代码如下。

顺便问一句:键—值对的添加顺序重要吗?换言之,如果你这样编写代码:

而不是这样编写代码:

对结果有影响吗?

只要回顾一下前一章介绍的内容,你就知道没影响。散列表是无序的,因此添加键—值对的顺序无关紧要。

Anuj、Peggy、Thom和Jonny都没有邻居,这是因为虽然有指向他们的箭头,但没有从他们出发指向其他人的箭头。这被称为有向图(directed graph),其中的关系是单向的。因此,Anuj是Bob的邻居,但Bob不是Anuj的邻居。无向图(undirected graph)没有箭头,直接相连的节点互为邻居。例如,下面两个图是等价的。

实现算法

先概述一下这种算法的工作原理。

首先,创建一个队列。在Python中,可使用函数deque来创建一个双端队列。

别忘了,graph[“you”]是一个数组,其中包含你的所有邻居,如[“alice”, “bob”, “claire”]。这些邻居都将加入到搜索队列中。

下面来看看其他的代码。

最后,你还需编写函数person_is_seller,判断一个人是不是芒果销售商,如下所示。

这个函数检查人的姓名是否以m结尾:如果是,他就是芒果销售商。这种判断方法有点搞笑,但就这个示例而言是可行的。下面来看看广度优先搜索的执行过程。

这个算法将不断执行,直到满足以下条件之一:

找到一位芒果销售商;

队列变成空的,这意味着你的人际关系网中没有芒果销售商。

Peggy既是Alice的朋友又是Bob的朋友,因此她将被加入队列两次:一次是在添加Alice的朋友时,另一次是在添加Bob的朋友时。因此,搜索队列将包含两个Peggy。

但你只需检查Peggy一次,看她是不是芒果销售商。如果你检查两次,就做了无用功。因此,检查完一个人后,应将其标记为已检查,且不再检查他。如果不这样做,就可能会导致无限循环。假设你的人际关系网类似于下面这样。

检查一个人之前,要确认之前没检查过他,这很重要。为此,你可使用一个列表来记录检查过的人。考虑到这一点后,广度优先搜索的最终代码如下。

运行时间

如果你在你的整个人际关系网中搜索芒果销售商,就意味着你将沿每条边前行(记住,边是从一个人到另一个人的箭头或连接),因此运行时间至少为O(边数)。你还使用了一个队列,其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的,即为O(1),因此对每个人都这样做需要的总时间为O(人数)。所以,广度优先搜索的运行时间为O(人数 + 边数),这通常写作O(V + E),其中V为顶点(vertice)数,E为边数。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180531A1QMEC00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券