廣度優先算法的實現

Question

我試圖實現一個「廣度優先」算法，作爲我在書中看到的某種變體。

我的問題是算法沒有將每個節點的元素添加到隊列中。

舉例來說，如果我搜索的「黑實驗室」之稱的「瑪麗拉」下的「搜索（）」函數，我會得到正確的輸出：「西蒙是個黑實驗室」

然而，我應該能夠在「walter」中找到「黑色實驗室」，它與連接到「simon」的「mariela」連接，「simon」是一個「黑色實驗室」，這是行不通的。有我在執行這個算法做了新手的錯誤，或者設置我的圖錯了嗎？

與往常一樣，任何/所有幫助深表感謝！

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和算法都是明智的。

改寫爲：

# @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