Python przeszukiwanie wszerz optymalizacja

Question

Biorąc pod uwagę ten kod ...

import Queue 

def breadthFirstSearch(graph, start, end): 
    q = Queue.Queue() 
    path = [start] 
    q.put(path) 
    while not q.empty(): 
     path = q.get() 
     lastNode = path[len(path) - 1] 
     if lastNode == end: 
      return path 
     for linkNode in graph[lastNode]: 
      if linkNode not in path: 
       newPath = [] 
       newPath = path + [linkNode] 
       q.put(newPath) 

Jeżeli wykres jest słownikiem reprezentującej graf skierowany, np {'stack':['overflow'], 'foo':['bar']} czyli stos skierowaną do przepełnienia i foo jest skierowaną do baru.

Czy ta szerokość pierwszego wyszukiwania może być zoptymalizowana bardziej? Ponieważ planuję użyć go na bardzo dużym słowniku.

Answer 1

Dlaczego nie przechowywać zestawu odwiedzanych węzłów, aby nie uderzać w te same węzły? To powinno działać, ponieważ nie wygląda na to, że używasz ważonego wykresu. Coś takiego:

import Queue 

def bfs(graph, start, end): 
    q = Queue.Queue() 
    path = [start] 
    q.put(path) 
    visited = set([start]) 

    while not q.empty(): 
     path = q.get() 
     last_node = path[-1] 
     if last_node == end: 
      return path 
     for node in graph[last_node]: 
      if node not in visited: 
       visited.add(node) 
       q.put(path + [node])