depth and breadth first search 問題

看板Python作者Luos (Soul)時間16年前 (2009/02/26 05:25)推噓1(1推 0噓 3→)

留言4則, 3人參與討論串1/1

各位大大好.... python學習歷經2個月受到各位大力幫忙實在非常感謝~~~ 如今再次遇到危機了>"< 我必須要用breadth first search 或 depth first search 來找 path breadth first search 只有辦法回傳 hop的數量但沒辦法回傳path 以下是我的breadth first search 得程式.. def bfs(self, top_node, bottom_node): visited = [] visited_parent = [] hop = 0 queue = deque([top_node]) while queue: curr_node = queue.popleft() if curr_node in visited: continue if curr_node == bottom_node: print "found path from " + top_node.node_num + " to " + bottom_node.node_num + " with visited " self.hop_matrix[int(top_node.node_num)].append(hop) break visited.append(curr_node) if len(queue) == 0 or curr_node == queue[0]: hop = hop + 1 queue.extend(curr_node.neighber_list) 但是不管怎麼試都沒辦法回傳path... 感謝wikipedia提供的範例~ depth first search 回傳path時會連我不想要的node都加進去..... 以下是我的depth first search def dfs(node, target, path): if node.value == target.value: return path else: path.append(node) for neighber in node.neighber_list: if not neighber in path: temp_path = dfs(neighber, target, path) 當找到時回傳的path會蓋掉原本的path... 這問題一直修不好... 坦白說吧這兩個都寫的很不好=.= 想請教一下各位大大有沒有比較好的寫法~~ 感謝各位大力幫忙XD -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 128.223.178.4