- 广度优先搜索指出是否有A到B的路径
- 如果有，广度优先搜索将找出最短的路径
面临类似于找最短路径的问题时，可以尝试使用图来建立模型，再使用广度优先搜索来解决问题。
应用实例
假设你经营这一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在Facebook，你与芒果销售商有联系吗？为此，你可在朋友中查找，这种查找很简短。首先创建一个朋友名单，然后依次检查名单中的每个人，假设你没有朋友是销售商，那你就有必要在朋友的朋友中查找。检查名单中的每个人时，你都将其朋友加入名单。
这样一来，你不仅在朋友中查找，还在朋友的朋友中查找。你的目标是在你的人际关系网中找到一位芒果销售商。因此，如果Alice不是芒果销售商，就将其朋友也加入到名单中。这意味着你将在他的朋友，朋友的朋友中查找。使用这种算法将搜索遍你的整个人际关系网，直到找到芒果销售商。这就是广度优先搜索算法。下面的程序就是对该实例的算法实现。
# encoding: utf-8
from collections import deque
#判断一个人是不是芒果销售商
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
if __name__ == "__main__":
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"]=[]
search("you")
