广度优先搜索---算法图解
学习目标
学习使用新的数据结构图来建立网络模型
什么是图？
假设你的关系网就理解为一个图，我们来探讨下面的问题。
学习广度优先搜索，你可以对图使用这种算法回答诸如“到x的最短路径问题”
从第一个点走到最后一个点 我们可以有很多的路径 找出一条最短的也就是最最短路径为问题
在我们之前介绍了二分搜索；今天的广度优先搜索是一种用于图的查找算法。
第一类问题：从A节点出发，存在前往B节点的路径吗
第二类问题：从节点A出发，前往B节点哪条路径最短
先举一个例子：
假如你经营着一个芒果农场，需要寻找芒果销售商将芒果卖出去。
这时候你可以从你的电话本中把你所有的朋友罗列出来然后依次排查就可以了
但是假如你的朋友中没有一个是芒果商 那么你就必须从你朋友的朋友中排查
于是你会将你朋友的朋友都罗列出来，在依次排查 这就是所谓的广度优先遍历
这就是解决第了一类问题（从A到B有没有路，（你能不能找到销售商的问题））
下面是第二类问题
从A到B的最短问题。我们这次同样的用水果商的方式表示这个问题
哪个芒果经销商和你关系最近？
从刚才的查找中可以看出来我们并不是顺着一个朋友一直去问，而是先将关系好的全部问一遍再去问关系差的
所以我们在找到经销商的同时 那也是离我们关系最好的
这就是广度优先搜索
注意
但是，要想实现这样的目的 我们必须有一个询问的顺序清单。我们之前学习的递归是顺着一直往下走，这样的话或许你可以找到水果销售商，他并不一定是和你关系最好的。
假如我们将关系分层，最好的为1层 依次递增。
我们必须先将一层的全部搜索完再往下一层。而递归本身是一直往下一层知道到底然后往回走。也就是利用了栈的特点。
如果想实现先搜索完没每一层再往下走，就需要与之对应的数据结构对列。
对列
类似与我们平时的排队方式谁先排谁就可以先上车离开。（也就是一种先入先出的数据结构）
知道这个后我们开始出来
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]#将你的邻居都加入到这个搜索队列中
print(search_queue)
searched = []#这个数组用于记录检查过的人
while search_queue:#只要队列不为空
person = search_queue.popleft()#取出队列中的一个人
print(person)
print(search_queue)
if person not in searched:#仅当这个人内检查过时才检查
if person_is_seller(person):#检查这个人是否是芒果销售商
print(person + " is a mango seller!")
return True
else:
search_queue += graph[person]#不是芒果销售商，将这个人的朋友都加入搜索队列
print(search_queue)
searched.append(person)#将这个人标记为检查过
print(searched)
== 值得注意的是必须检查有没有检查过这个人，因为这个人可能与你也有关系，这样就会陷入一个无线循环==