美文网首页
非加权图中查找最短路径--广度优先搜索

非加权图中查找最短路径--广度优先搜索

作者: 还是那个没头脑 | 来源:发表于2020-03-04 16:22 被阅读0次
    from collections import deque
    
    graph = {}
    graph["you"] = ["小明","小红","小黄"]
    graph["小明"] = []
    graph["小红"] = []
    graph["浅黄"] = []
    graph["土黄"] = []
    graph["深黄"] = []
    graph["小黄"] = ["浅黄","土黄","深黄"]
    
    def person_is_seller(name):
        return name[0] =='土'
    
    def search(name):
        search_queue = deque()
        search_queue += graph[name]
        searchd = []
        while search_queue:
            person = search_queue.popleft()
            if person not in searchd:
                if person_is_seller(person):
                    print(f'找到了{person}')
                    return True
                else:
                    search_queue += graph[person]
                    searchd.append(person)
        return False
    
    search("you")
    

    运行时间O(人数+边数),通常写作O(V+E),V为顶点数,E为边数

    相关文章

      网友评论

          本文标题:非加权图中查找最短路径--广度优先搜索

          本文链接:https://www.haomeiwen.com/subject/iffblhtx.html