广度优先算法

deque 即双端队列。是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

# 最短路径问题的算法被称为广度优先搜索
# 广度优先搜索是一种用于图的查找算法
# 第一类问题：从节点A出发，有前往节点B的路径吗？
# 第二类问题：从节点A出发，前往节点B的哪条路径最近。
from collections import deque
graph={}
graph['you']=['alice','bob','claire']
graph['bob']=['anuj','peggy']
graph['alice']=['thom','jonny']
graph['claire']=['them','jonny']
graph['anuj']=[]
graph['peggy']=[]
graph['them']=[]
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 person not in searched:
            if person_is_seller(person):
                print(person+" is a mango seller!")
                return True
            else:
                search_queue+=graph[person]
                # 将这个人标记为检查过
                searched.append(person)
        print(searched)
    return False
search("you")

code result

['alice']
['alice', 'bob']
['alice', 'bob', 'claire']
thom is a mango seller!