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

前言

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

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

第一类问题：从节点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为边数。