假如我想阅读一本名为《Python数据结构》的书籍，这个时候需要通过朋友去借，我的朋友也可以通过他们的朋友帮我去借，那么我怎么样通过最少的人际关系接到这本书，这就是最短路径问题。解决最短路径问题的算法被称为广度优先搜索。
广度优先搜索可以回答两类问题：
1.从节点A出发，有前往B节点的路径吗？（在人际关系中，就是有人有这本书吗）
2.从节点A出发，前往节点B的哪条路径最短？(我通过最少的朋友接到这本书)
在借书这个过程中，朋友是一度关系，朋友的朋友是二度关系，以此类推。一度关系胜于二度关系，二度关系胜于三度关系。
因此，在广度优先搜索中，要确定一度关系没有书籍，再去搜索二度关系。
因此，需要按添加顺序进行检查，这里可以使用队列进行设计。
对于检查过的人，务必不要再去检查，否则可能导致无限循环。
#使用函数deque来创建一个双端队列
from collections import deque
graph = {}
#我的朋友
graph['you'] = ['alice', 'bob', 'claire']
#朋友的朋友
graph['alice'] = ['anuj', 'peggy']
graph['bob'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []
def person_has_book(name):
return name[-1] == 'm'
def test(graph):
#创建一个队列
search_queue = deque()
#将你的朋友都加入到搜索这个队列中
search_queue += graph['you']
#这个数组用于记录检查过的人
searched = []
#只要队列不为空
while search_queue:
#就取出其中的第一个人
person = search_queue.popleft()
#仅当这个人没检查过时才检查
if person not in searched:
# 检查这个人是否有书
if person_has_book(person):
print(person + "has this book")
return True
#如果没有书。将这个人的朋友都加入到搜索队列中
else:
search_queue += graph[person]
searched.append(person)#将这个人标记为检查
return False
print(test(graph))
