参考： https://www.cn blogs.com/Tianqi zhi/p/9914539.html
宽度优先搜索算法(也称为宽度优先搜索)是最简便的图的搜索算法之一，该算法也是许多重要图的算法原型。 Dijkstra单源最短路径算法和Prim最小生成树算法都采用与广度优先搜索相似的思想。 别名又称BFS(Breadth-firstsearch )，是一种以系统展开图中所有节点进行检测并找到结果为目的的盲目搜索方法。 也就是说，不考虑结果的可能位置，而是彻底搜索整个图直到找到结果。 在广度优先搜索中，可以找到两个东西之间的最短距离，但最短距离的意义有很多！ 首先介绍什么是图，然后介绍第一个图算法——广度优先搜索算法。 1 .图片简介假设你住在旧金山，从双子峰去金门大桥。 我想坐巴士去，希望换乘最少。 能乘坐的巴士如下。
为了找到换乘最少的乘车路线，用什么算法？
一步能到达金门大桥吗？ 我强调了一步能去的所有地方。
金门大桥不突出，所以一步也到不了那里。 两步可以吗？
金门大桥也不突出，所以两步都到不了。 三步走？
金门大桥突出！ 所以从双子峰出发，沿着下一条路线三步就到金门大桥。
虽然还有其他通往金门大桥的路线，但是它们更远(需要四步)。
该算法发现，通往金门大桥的最短路径需要三步。 这种问题被称为最短路径问题(shorterst-path problem )。 你必须经常找到最短的路径。 这可能是去朋友家的最短路径，也可能是下国际象棋堵塞对方的最低手续费。
解决最短路径问题的算法称为幅度优先搜索。 要确定如何从双子峰去金门大桥，需要两个步骤：
(1)用图建立问题模型
(2)使用广度优先搜索解决问题。
什么是图？图由节点（node）和边（edge）组成。一个节点可能与众多节点直接相连，这些直接相连的节点被称为邻居。图用于模拟不同的东西是如何相连的。
2 .广度优先搜索算法广度优先搜索是一种面向图的搜索算法，有助于回答两类问题。
类型1问题：是否有从节点a出发到节点b的路径？
类型2问题：从节点a出发到节点b的哪个路径最短？
在先计算双子峰到金门大桥的最短路线时，已经使用过宽度优先搜索。 这个问题是第二类问题。 哪个路径最短？ 让我们仔细研究一下这个算法。 用它来回答第一个问题。 有传球吗？
假设你在经营芒果农场，需要找芒果分销商把芒果卖给他。 为此，你可以在朋友中寻找。
这个搜索很简单。 首先，列一个朋友列表。
然后，按顺序检查名单上的所有人，看看是否是芒果销售商。
如果没有芒果销售商的朋友，就必须在朋友的朋友中找。
检查名单上的所有人时，你把那个朋友添加到名单上。
2.1找最短的路线再说一遍。 广度优先搜索可以回答两种类型的问题。
类型1问题：是否有从节点a出发到节点b的路径？ )你的人际关系网上有芒果经销商吗？ ）
类型2问题：从节点a出发到节点b的哪个路径最短？ 哪个芒果经销商和你关系最近？ ）
我刚才看到了怎么回答第一个问题，让我们来回答第二个问题——吧。 最近的芒果经销商是谁？ 例如，朋友是一次关系，朋友的朋友是两次关系。
在你看来，一次关系胜于二次关系，二次关系胜于三次关系，由此类推。 因此，请搜索一次关系，确保没有芒果销售商，然后再搜索两次关系。 广度优先搜索就是这样做的！
在宽度优先搜索的执行中，搜索范围从起点逐渐向外侧延伸。 也就是说，先检查一次关系，再检查两次关系。 顺便问一下，你要先检查ddqd还是Anuj？ dqd是一次关系，但Anuj是两次关系，所以首先检查ddqd，然后检查Anuj。
也可以这样看。 一次关系在两次关系之前加入搜索列表。 请按顺序检查名单上的所有人，看看他是否是芒果销售商。 因为这是一次关系找，然后是两次关系找，所以找到的是最有关系的芒果经销商。
宽度优先搜索不仅找到从a到b的路径，还找到最短的路径。
注意：只有按添加顺序查找时，才能实现这样的目的。换句话说，如果ddqd先于Anuj加入名单，就需要先检查ddqd，再检查Anuj。如果ddqd和Anuj都是芒果销售商，而你先检查Anuj再检查ddqd，结果将如何呢？找到的芒果销售商并非是与你关系最近的，因为Anuj是你朋友的朋友，而ddqd是你的朋友。因此，你需要按添加顺序进行检查。有一个可实现这种目的的数据结构，那就是队列（queue）。
2.2队列的结构与实际生活中的队列完全相同。 假设你和朋友一起在公共汽车站排队。 如果你排在他前面的话，我先上车。 队列的结构与此相同。 队列就像堆栈，不能随机访问队列中的元素。 队列只支持入队和出队两种操作。
将两个元素添加到队列中时，先添加的元素将在后添加的元素之前退出队列。 所以，你可以使用队列查找列表！ 这样，先参加的人先出队先被检查。
队列是先进的先进先出(
First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。知道队列的工作原理后，我们来实现广度优先搜索！ 3. 实现 图
首先，需要使用代码来实现图。图由多个节点组成，每个节点都与邻近节点相连。如何表示类似于“你→tmdc”这样的关系呢？好在你知道的一种结构让你能够表示这种关系，它就是散列表！
记住，散列表让你能够将键映射到值。在这里，你要将节点映射到其所有邻居。
表示这种映射关系的Python代码如下：
graph = {}
graph[“you”] = [“舒服的野狼”, “bob”, “傲娇的雪碧”]
注意，“你”被映射到了一个数组，因此graph[“you”]是一个数组，其中包含了“你”的所有邻居。
图不过是一系列的节点和边，因此在Python中，只需使用上述代码就可表示一个图。那像下面这样更大的图呢？
表示它的Python代码如下：
顺便问一句：键—值对的添加顺序重要吗？换言之，如果你这样编写代码：
graph["傲娇的雪碧"] = ["thom", "jonny"]graph["anuj"] = []而不是这样编写代码：
graph["anuj"] = []graph["傲娇的雪碧"] = ["thom", "jonny"]对结果有影响吗？只要回顾一下以前介绍的内容，你就知道没影响。散列表是无序的，因此添加键—值对的顺序无关紧要。
Anuj、爱听歌的银耳汤、Thom和Jonny都没有邻居，这是因为虽然有指向他们的箭头，但没有从他们出发指向其他人的箭头。这被称为有向图（directed graph），其中的关系是单向的。因此，Anuj是tmdc的邻居，但tmdc不是Anuj的邻居。无向图（undirected graph）没有箭头，直接相连的节点互为邻居。例如，下面两个图是等价的：
先概述一下这种算法的工作原理：
首先，创建一个队列。在Python中，可使用函数deque来创建一个双端队列：
别忘了，graph[“you”]是一个数组，其中包含你的所有邻居，如[“舒服的野狼”, “bob”, “傲娇的雪碧”]。这些邻居都将加入到搜索队列中。
下面来看看其他的代码：
下面来看看广度优先搜索的执行过程：
这个算法将不断执行，直到满足以下条件之一：
（1）找到一位芒果销售商；
（2） 队列变成空的，这意味着你的人际关系网中没有芒果销售商。
爱听歌的银耳汤既是迷人的白昼的朋友又是tmdc的朋友，因此她将被加入队列两次：一次是在添加迷人的白昼的朋友时，另一次是在添加tmdc的朋友时。因此，搜索队列将包含两个爱听歌的银耳汤。但你只需检查爱听歌的银耳汤一次，看她是不是芒果销售商。如果你检查两次，就做了无用功。因此，检查完一个人后，应将其标记为已检查，且不再检查他。如果不这样做，就可能会导致无限循环。假设你的人际关系网类似于下面这样：
一开始，搜索队列包含你的所有邻居：
现在你检查爱听歌的银耳汤。她不是芒果销售商，因此你将其所有邻居都加入搜索队列：
接下来，你检查自己。你不是芒果销售商，因此你将你的所有邻居都加入搜索队列：
以此类推。这将形成无限循环，因为搜索队列将在包含你和包含爱听歌的银耳汤之间反复切换：
检查一个人之前，要确认之前没检查过他，这很重要。为此，你可使用一个列表来记录检查过的人。
考虑到这一点后，广度优先搜索的最终代码如下：
如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一个人到另一个人的箭头或连接），因此运行时间至少为O(边数)。你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为O(1)，因此对每个人都这样做需要的总时间为O(人数)。所以，广度优先搜索的运行时间为O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。
5. 小结： 广度优先搜索指出是否有从A到B的路径。如果有，广度优先搜索将找出最短路径。面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题。有向图中的边为箭头，箭头的方向指定了关系的方向，例如， rama→adit 表示 rama 欠 adit 钱。无向图中的边不带箭头，其中的关系是双向的，例如， ross - 专一的夏天 表示 ross 与 专一的夏天 约会，而 专一的夏天 也与 ross 约会。队列是先进先出（FIFO）的。栈是后进先出（LIFO）的。你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。对于检查过的人，务必不要再去检查，否则可能导致无限循环。