アルゴリズム図解第六章広さ優先検索読書ノート


  • 図はノードとエッジからなる.1つのノードは、隣接ノードと呼ばれる多くのノードに直接接続することができる.
  • 広さ優先検索は図の検索アルゴリズムであり、2つの質問に答えるのに役立つ:1)ノードAからノードBへの経路はありますか?2)ノードAからノードBへの最短経路はどれですか.
  • 有向図と無向図(矢印なし、直接接続されたノードは互いに隣接する)
  • トポロジ順序
  • ツリーは特殊な図
  • である.
  • 広さ優先探索アルゴリズム
  • from collections import deque
    graph = {}
    graph["you"] = ["alice", "bob", "claire"]
    graph["bob"] = ["anuj", "peggy"]
    graph["alice"] = ["peggy"]
    graph["claire"] = ["thom", "jonny"]
    graph["anuj"] = []
    graph["peggy"] = []
    graph["thom"] = []
    graph["jonny"] = []
    
    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)
        return False
    
    
    def person_is_seller(nname):
        return nname[-1] == 'm'
    
    search("you")