Python Queue.Queue et consistance cohérente?

Question

Compte tenu de ce code ...

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]) 

Où graphique est un dictionnaire qui représente un graphe orienté, par exemple, { 'pile': [ 'débordement'], 'foo': [ 'bar']} par exemple, la pile pointe vers le débordement et foo pointe vers la barre. Pourquoi ne reçois-je pas le même résultat lorsque je remplace Queue.Queue par deque dans les collections pour augmenter l'efficacité?

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]) 

Answer 1

Votre version Queue.Queue utilise FIFO alors que votre version deque utilise FILO. Vous devez utiliser path = q.popleft() à la place pour résoudre ce problème.

Notez que Queue.Queue utilise en interne un deque sous-jacent pour représenter la file d'attente. Pour plus d'informations, voir le relevant documentation (voir _get méthode)