问题:在人际关系网中通过最少的人找到芒果经销商。
分析:
1.创建一个队列,用于存储要检查的人;
2.从队列中弹出一个人;
3.检查这个人是否是芒果经销商,如果是,将就找到了,否则执行第4步;
4.把这个人的所有邻居加入队列;
5.执行第2步;
6.如果队列为空,则没找到。
graph = {}
graph["you"] = ["a", "b"]
graph["a"] = ["c", "d"]
graph["b"] = ["f"]
graph["c"] = []
graph["d"] = ["f"]
graph["f"] = ["mogo_seller"]
def person_is_seller(name):
if 'mogo' in name:
return True
else:
return False
from collections import deque
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('find:', person)
return True
else:
search_queue += graph[person]
searched.append(person)
return False
assert search("you") == True