Python Queue.Queue和双端队列的一致性？

Question

给定此代码...

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']}，即，堆栈指向溢出，而foo指向bar。

为什么将queque.Queue替换为来自集合的双端队列以提高效率，为什么我没有得到相同的结果？

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

您的Queue.Queue版本使用FIFO，而您的deque版本使用FILO。您应该改用path = q.popleft()此方法来解决此问题。请注意，Queue.Queue内部使用基础deque来表示队列。有关更多信息，请参见相关文档（请参阅_get方法）