**算法图解第六章-广度优先搜索**

##### 1.1、广度优先搜索 

广度优先搜索让你能够找出两样东西之间的**最短距离**，最短距离的含义有很多，使用广度优先搜索可以：

1.    高德地图最短路径获取
2.    英雄联盟轨迹计算
3.    编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将readed改为reader需要编辑一个地方；
4. 根据你的人际关系网络找到关系最近的医生。



##### 1.2、图简介-最短路径问题 

**图简介**：图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。连接表示不同节点之间的关系，关系可以根据具体的问题进行定义。

最短路径：假设你居住在双子峰，要从双子峰前往金门大桥。你想乘公交车前往，并希望**换乘最少**。可乘坐的公交车如下

![img](https://ss1.baidu.com/6ONXsjip0QIZ8tyhnq/it/u=3388605196,689420357&fm=173&app=49&f=JPEG?w=640&h=262&s=7AAC3C62859049C20CD534CB0000A0B1)

这就构成一个图，**地点**是图中的节点，连接表示不同节点之间是否存在公交车的关系

> 当然，这只是图的一个例子，图可以表示不同节点之间的关系，节点可以有多种含义。

你希望从最短的路径，花最少的时间到达金山大桥，按照这个图，你需要走最少三步，这就是最短路径，如下所示：

![img](https://ss1.baidu.com/6ONXsjip0QIZ8tyhnq/it/u=2997508255,1803148940&fm=173&app=49&f=JPEG?w=640&h=262&s=7AAC3C628788594116FDD1CE0000A0B1)

**6.3、广度优先搜索**

解决最短路径问题的算法被称为广度优先搜索，广度优先搜索是一种用于图的查找算法，可回答两类问题

第一类问题：从节点A出发，有前往节点B的路径吗？

第二类问题：从节点A出发，前往节点B的哪条路径最短？

解决第一类问题：

从节点A，查找节点A的所有邻居中是否有B,如果没有再查找A的邻居的邻居中是否有B,一直查找下去，直到找到B或者遍历完。

**（1）是否存在问题：**

以寻找销售商的例子说明：

假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在微信，你与芒果销售商有联系吗？为此，你可在朋友中查找。

首先，创建一个朋友表单，依次检查名单中的每个人，看看他是否是芒果销售商？

![img](https://ss0.baidu.com/6ONWsjip0QIZ8tyhnq/it/u=1774771830,2937918546&fm=173&app=49&f=JPEG?w=498&h=502&s=3AAA742359EFE0CE5A5500DA0000C0B1)

如果你的朋友中没有销售商，那就检查名单中每个朋友的朋友有没有销售商。

![img](https://ss2.baidu.com/6ONYsjip0QIZ8tyhnq/it/u=3269043245,3427498168&fm=173&app=49&f=JPEG?w=640&h=188&s=1AAA7423C77448231EFC91CE0000E0B1)

这样，你就能知道你的关系网中有没有销售商，这样，你就解决了存不存在的问题。

**（2）查找最短路径**

什么是最短路径？

在上面的例子中，如果你的朋友定义为一度关系，你的朋友的朋友定义为二度关系，依此而定，一度关系比二度关系更加亲密，距离更短。为了寻找最短路径，一般先从一度关系开始找起，若一度关系中找不到想要的，再开始找二度关系，编程中如何实现这种顺序，则是利用队列来完成。

![img](https://ss0.baidu.com/6ONWsjip0QIZ8tyhnq/it/u=2601404646,3495327712&fm=173&app=49&f=JPEG?w=465&h=369&s=5AAA34621BABC4CE5CF460DA0000C0B1)

**6.4、编程实现**

**（1）队列-控制顺序：**

队列是一种先进先出的数据结构，它支持入队和出队两种操作，并且先进先出。

![img](https://ss0.baidu.com/6ONWsjip0QIZ8tyhnq/it/u=3122813475,79404497&fm=173&app=49&f=JPEG?w=446&h=199&s=1AAA7C23439469C05CFD51DE0000A0B1)

**（2）图的实现-散列表**

散列表根据键值的方式存储节点间的相邻关系，对于下方这幅图，

![img](https://ss1.baidu.com/6ONXsjip0QIZ8tyhnq/it/u=2677352677,1647118348&fm=173&app=49&f=JPEG?w=499&h=377&s=1AAA7C2241EAD0EE1CFCA0DA0000E0B1)

python代码表示图：（注意散列表是无序的）

![img](https://ss2.baidu.com/6ONYsjip0QIZ8tyhnq/it/u=3973196567,4007022154&fm=173&app=49&f=JPEG?w=463&h=215&s=8C50E41209C04C430C75E4DA0000C0B2)

**（3）实现寻找芒果销售商的程序：**

![img](https://ss0.baidu.com/6ONWsjip0QIZ8tyhnq/it/u=1817363844,419376354&fm=173&app=49&f=JPEG?w=640&h=771&s=7AAC3C62197FE4CC4E5D55CF0000C0B1)

**python代码：**

![img](https://ss1.baidu.com/6ONXsjip0QIZ8tyhnq/it/u=2905031440,1430758817&fm=173&app=49&f=JPEG?w=640&h=306&s=800875321B0244490EDDC5DA0000C0B1)

**6.5、运行时间：**

广度优先搜索的运行时间为：O(人数 + 边数)

**6.6、总结：**

（1）广度优先搜索解决是否存在从A到B的路径的问题，如果有，广度优先搜索将找出最短路径。

（2）寻找最短路径的问题，可以建立图关系，利用广度优先搜索算法求解

（3）广度优先搜索，利用队列的结构，先从开始节点的邻居开始遍历，先检索一个节点是否满足要求，若满足要求，则结束搜索，若不满足则将该节点弹出队列，将该节点的邻居加入队列，最终完成遍历或找到满足要求的节点。