Britth-First-Algorithmus-Implementierung

Question

Ich versuche, einen "Breite-zuerst" -Algorithmus als eine Variation von etwas, das ich in einem Buch gesehen habe, zu implementieren.

Mein Problem ist, dass der Algorithmus die Elemente jedes Knotens nicht in die Warteschlange einfügt.

Zum Beispiel, wenn ich für „black lab“ unter dem Namen ‚mariela‘ in der „Suche()“ Funktion zu suchen, werde ich die richtige Ausgabe: „Simon ist ein schwarzes Labor“

jedoch Ich sollte nach "black lab" in "walter" suchen können, das mit "mariela" verbunden ist, das mit "simon" verbunden ist, der ein "schwarzes Labor" ist. Das funktioniert nicht.

Habe ich einen Anfängerfehler in meiner Implementierung dieses Algorithmus gemacht, oder habe ich mein Diagramm falsch eingerichtet?

Wie immer wird jede/alle Hilfe sehr geschätzt!

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

Sie haben viele Probleme in Ihrer Implementierung - sowohl Python als auch Algorithmic.

Rewrite als:

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

Hier ist eine Demo https://repl.it/IkRA/0