广度优先搜索-芒果经销商问题

问题:在人际关系网中通过最少的人找到芒果经销商。
分析:
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
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容