摘要：解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由年在如何从迷宫中寻找出路这一问题中提出。广度优先搜索让你能够找出两样东西之间的最短距离。使用广度优先搜索解决问题。
你经常需要解决最短路径问题(shorterst-path problem)。解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由Edward F. Moore 1959年在“如何从迷宫中寻找出路”这一问题中提出。
广度优先搜索让你能够找出两样东西之间的最短距离。使用广度优先搜索可以:
编写国际跳棋AI,计算最少走多少步就可获胜;
编写拼写检查器,计算最少编辑多少个地方就可将错拼的单词改成正确的单词,如将READED改为READER需要编辑一个地方;
根据你的人际关系网络找到关系最近的医生。
要解决最短路径问题，需要两个步骤。
使用图来建立问题模型。
使用广度优先搜索解决问题。
图是什么图用于模拟不同的东西是如何相连的。图由节点(node)和边(edge)组成。一个节点可能与众多节点直接相连,这些节点被称为邻居。树是一种特殊的图,其中没有往后指的边。
在图中，边用来表示节点之间的关系，若关系是有方向的，则图为有向图(directed graph)，此时图中的边有箭头。若关系没有方向，则图为无向图(undirected graph),此时图中的边没有箭头，直接相连的节点互为邻居。
如上图是有向图，Rama是Alex的邻居。
广度优先搜索是一种用于图的查找算法,可帮助回答两类问题。
第一类问题:从节点A出发,有前往节点B的路径吗?
第二类问题:从节点A出发,前往节点B的哪条路径最短?
两类问题并没有本质区别，在实现层面仅仅第二类需要携带路径的信息，因为最终通常需要返回这个路径。
示例：假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。
算法原理：
（1）创建一个朋友名单。
（2）依次检查名单中的每个人,看看他是否是芒果销售商。
（3）假设你没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找。检查名单中的每个人时,你都将其朋友加入名单。
若找到，则表示你与芒果销售商有联系；由于在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系，我们找到的芒果销售商也是关系最近的。
执行过程中，一度关系在二度关系之前加入查找名单，所以我们优先检查一度关系，然后才到二度，依次进行。这需要存储名单的数据结构有“先进先出”的特性，这种数据结构就是队列(queue)。
队列类似于栈,队列也是一种操作受限的数据结构，你不能随机地访问队列中的元素。队列只支持两种操作:入队和出队。
队列是一种先进先出(First In First Out,FIFO)的数据结构,而栈是一种后进先出(Last In First Out,LIFO)的数据结构。
实现图使用散列表存储每个节点与邻近节点关系。
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
实现算法
算法的工作原理：
一点需要注意：检查一个人之前,要确认之前没检查过他,这很重要，因为有可能会导致无限循环。
完整算法如下：
from collections import deque
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
def person_is_seller(name):
return name[-1] == "m"
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = []
while search_queue:
person = search_queue.popleft()
if not person in searched:
if person_is_seller(person):
print(person + " is a mango seller!")
return True
else:
search_queue += graph[person]
searched.append(person)
return False
search("you")
算法的时间复杂度：O(V + E)，其中V为顶点(vertice)数,E为边数。
请继续关注我的公众号文章
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/43589.html
递归是个有意思的概念，正如在前面所说，递归能让算法的可读性大大提高，而且通常要比使用循环结构更能写出准确的算法。这本书形象引入了递归，并没有太深入，所以我进行了一点添油加醋。 递归 概念 递归其实就是自己调用自己。可以从多种维度对递归分类，我见过的最常见的分类： 直接递归 自己直接调用自己。如： --haskell length :: [a] -> Int length [] = 0 length...
摘要：散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中，我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现，利用递归和广度优先搜索的思想实现。 什么是广度优先搜索？ 如果只是是背概念，幼儿园的小朋友都能背下来念给你听。 假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（BFS）中学到什么...
阅读 3622·2021-11-24 10:22
阅读 3689·2021-11-22 09:34
阅读 2492·2021-11-15 11:39
阅读 1530·2021-10-14 09:42
阅读 3665·2021-10-08 10:04
阅读 1556·2019-08-30 15:52
阅读 851·2019-08-30 13:49
阅读 3018·2019-08-30 11:21
