このコードを考えると...
import Queue
def breadthFirstSearch(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])
ここで、graph は有向グラフを表す辞書です。たとえば、{'stack':['overflow'], 'foo':['bar']} です。つまり、stack はオーバーフローを指し、foo は bar を指します。
効率を上げるために Queue.Queue をコレクションからの deque に置き換えても、同じ結果が得られないのはなぜですか?
from collections import deque
def breadthFirstSearch(graph, start, end):
q = deque()
path = [start]
q.append(path)
visited = set([start])
while q:
path = q.pop()
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.append(path + [node])