幅優先アルゴリズムの実装

Question

私は本で見たことのバリエーションとして "幅優先"アルゴリズムを実装しようとしています。

私の問題は、アルゴリズムがすべてのノードの要素をキューに追加していないことです。例えば

私は「検索（）」機能に「マリエラ」の名前の下に「黒ラボ」を検索すると、私は正しい出力が得られます：「サイモンは黒ラボで」

をしかし、私は "マリエラ"に接続されている "ウォルター"で "黒い研究室"を探すことができなければなりません。 "マリエラ"は "サイモン"に接続しています。私はこのアルゴリズムの実装に新人の間違いをしたのですか、または私のグラフを間違って設定しましたか？

いつもどんな助けがありますか？

from collections import deque 


# TEST GRAPH ------------- 
graph = {} 
graph['walter'] = ['luci', 'kaiser', 'andrea', 'mariela'] 
graph['andrea'] = ['echo', 'dante', 'walter', 'mariela'] 
graph['mariela'] = ['ginger', 'simon', 'walter', 'andrea'] 
graph['kaiser'] = 'german shepherd' 
graph['luci'] = 'black cat' 
graph['echo'] = 'pitbull' 
graph['dante'] = 'pitbull' 
graph['ginger'] = 'orange cat' 
graph['simon'] = 'black lab' 



def condition_met(name): 
    if graph[name] == 'black lab': 
     return name 


def search(name): 
    search_queue = deque() 
    search_queue += graph[name]    # add all elements of "name" to queue 
    searchedAlready = []     # holding array for people already searched through 

while search_queue:      # while queue not empty... 
    person = search_queue.popleft()  # pull 1st person from queue 
    if person not in searchedAlready: # if person hasn't been searched through yet... 
     if condition_met(person): 
      print person + ' is a black labrador' 
      return True 
    else: 
     search_queue += graph[person] 
     searchedAlready.append(person) 
return False 


search('walter') 
#search('mariela') 

Answer 1

あなたの実装には、PythonとAlgorithmの両方に問題があります。

書き換えなど：ここ

# @param graph graph to search 
# @param start the node to start at 
# @param value the value to search for 
def search(graph, start, value): 
    explored = [] 
    queue = [start] 
    while len(queue) > 0: 
    # next node to explore 
    node = queue.pop() 
    # only explore if not already explored 
    if node not in explored: 
     # node found, search complete 
     if node == value: 
     return True 
     # add children of node to queue 
     else: 
     explored.append(node) 
     queue.extend(graph[node]) # extend is faster than concat (+=) 
    return False 


graph = {} 
graph['walter'] = ['luci', 'kaiser', 'andrea', 'mariela'] 
graph['andrea'] = ['echo', 'dante', 'walter', 'mariela'] 
graph['mariela'] = ['ginger', 'simon', 'walter', 'andrea'] 

# children should be a list 
graph['kaiser'] = ['german shepherd'] 
graph['luci'] = ['black cat'] 
graph['echo'] = ['pitbull'] 
graph['dante'] = ['pitbull'] 
graph['ginger'] = ['orange cat'] 
graph['simon'] = ['black lab'] 

print search(graph, 'mariela', 'walter') 

がhttps://repl.it/IkRA/0