這個Python代碼是否使用深度優先搜索（DFS）來查找所有路徑？

此代碼在python official essays on graph theory中給出。這裏的代碼：這個Python代碼是否使用深度優先搜索（DFS）來查找所有路徑？

def find_all_paths(graph, start, end, path=[]): 
     path = path + [start] 
     if start == end: 
      return [path] 
     if not graph.has_key(start): 
      return [] 
     paths = [] 
     for node in graph[start]: 
      if node not in path: 
       newpaths = find_all_paths(graph, node, end, path) 
       for newpath in newpaths: 
        paths.append(newpath) 
     return paths

我不擅長python，因爲我還沒有足夠的練習和閱讀。您能否通過將此與DFS圖中的同胞概念相關聯來解釋代碼？謝謝。

來源

2010-11-20 Pupil

'paths.extend（newpaths）' – 2010-11-20 02:25:59

作爲參考，我總是會'不在圖中開始而不是在'無圖。 has_key（start）'（我假設'graph'是一個'dict'或類似的）。 – 2010-11-20 02:27:18

克里斯，是的'圖'是一個'字典'。 – Pupil 2010-11-20 02:28:04

看到它是DFS的關鍵是遞歸發生在路徑積累之前。換句話說，在將任何東西放在「路徑」列表中之前，遞歸將盡可能地深入。在返回列表之前，所有最深的兄弟姐妹在「路徑」上積累。

我相信代碼是正確的「附加」而不是「擴展」，因爲「路徑」是所有路徑的累加器。雖然它也許可以寫成

paths += find_all_paths(graph, node, end, path)

（編輯）...而不是

newpaths = find_all_paths(graph, node, end, path) 
for newpath in newpaths: 
    paths.append(newpath)

來源

2010-11-20 03:03:52 mjhm

感謝mjhm的回答。你能告訴哪裏包括你建議的'path + = find_all_paths（圖形，節點，結束，路徑）'這一行嗎？ – Pupil 2010-11-20 03:18:45

是的，這個算法確實是一個DFS。請注意，它是如何在循環遍歷各個節點時立即遞歸（進入孩子），而不是廣度優先搜索，它基本上會生成一個可行節點列表（例如，所有在同一深度級別上的兄弟姐妹）當那些不符合您的要求時遞歸。

來源

2010-11-20 02:59:42 Stigma

考慮以下修改和執行腳本：

def find_all_paths(graph, start, end, path=[]): 
    path = path + [start] 
    print 'adding %d'%start 
    if start == end: 
     return [path] 
    if not graph.has_key(start): 
     return [] 
    paths = [] 
    for node in graph[start]: 
     if node not in path: 
      paths.extend(find_all_paths(graph, node, end, path)) 
    print 'returning ' + str(paths) 
    return paths 

G = {1:[2,3,4], 2:[1,4], 3:[1,4], 4:[1,2,3]} 
find_all_paths(G, 1, 4)

輸出：

adding 1 
adding 2 
adding 4 
returning [[1, 2, 4]] 
adding 3 
adding 4 
returning [[1, 3, 4]] 
adding 4 
returning [[1, 2, 4], [1, 3, 4], [1, 4]]

注意如何在添加3之前返回第一個路徑，並且在添加4之前返回第二個路徑。

來源

2010-11-20 03:21:55

這個Python代碼是否使用深度優先搜索（DFS）來查找所有路徑？

回答

相關問題