推 liangjr:path是mutable所以會被改掉 02/26 10:05
→ Luos:今天去找老師...結果他用最直接的方法..在queue直接放一個pat 03/03 02:56
→ Luos:th list 進去 03/03 02:57
→ qrtt1:那就是資料結構課本寫的方法了啊 ha ha 03/03 21:17
各位大大好....
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