0

このコードを考えると...

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

1 に答える 1

2

あなたのQueue.Queueバージョンは FIFO を使用していますが、あなたのdequeバージョンは FILO を使用しています。path = q.popleft()これを修正するには、代わりに使用する必要があります。

キューを表すために基にQueue.Queueなるものを内部的に使用することに注意してください。deque詳細については、関連するドキュメントを参照してください (_getメソッドを参照)

于 2013-05-25T09:11:54.910 に答える