給定此代碼...import Queuedef 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])其中g(shù)raph是代表有向圖的字典,例如{'stack':['overflow'],'foo':['bar']},即,堆棧指向溢出,而foo指向bar。為什么將queque.Queue替換為來自集合的雙端隊列以提高效率,為什么我沒有得到相同的結(jié)果?from collections import dequedef 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])
1 回答

元芳怎么了
TA貢獻1798條經(jīng)驗 獲得超7個贊
您的Queue.Queue
版本使用FIFO,而您的deque
版本使用FILO。您應(yīng)該改用path = q.popleft()
此方法來解決此問題。
請注意,Queue.Queue
內(nèi)部使用基礎(chǔ)deque
來表示隊列。有關(guān)更多信息,請參見相關(guān)文檔(請參閱_get
方法)
添加回答
舉報
0/150
提交
取消