遞歸DFS函數的中間結果 - Python

我基本上試圖更好地理解遞歸。讓我們看看下面的DFS算法，該算法返回連接到基本根節點的所有節點。這種情況下的「圖形」被定義爲頂點之間邊的元組列表。遞歸DFS函數的中間結果 - Python

def dfs(graph,node,dfs_visited): 
    if node not in dfs_visited: 
     dfs_visited.append(node) 

     #find next node to go 
     potential_paths = [i for i in graph if node in i] 
     new_nodes = [node_ for path in potential_paths for node_ in 
        path if node_ !=node] 
     for n in new_nodes: 
      dfs(graph,n,dfs_visited) 
    return dfs_visited

例如，如果圖形是

graph = [(0, 1),(0, 2),(1, 2),(3, 4),(4,5)]

開始在節點0的結果將是

dfs(graph,0,[]) 
[0,1,2]

我在這種情況下，很好奇的是，這是結果來自遞歸調用中的一個的「返回」。很顯然，代碼的工作方式我打算，我對結果很好，但我只是好奇中間「回報」去哪裏。

dfs(graph,0,[]) 
returning [0, 1] 
returning [0, 1, 2] 
returning [0, 1, 2] 
returning [0, 1, 2] 
returning [0, 1, 2] 
returning [0, 1, 2] 
returning [0, 1, 2]

那麼，如何的Python知道其中哪一個是函數的實際輸出：例如，當我們返回的語句中，我們得到如下輸出前右運行與添加的打印語句同樣的功能？它只是最後一個？

來源

2017-08-10 user4505419

在這一行，你遞歸調用函數：

for n in new_nodes: 
    dfs(graph,n,dfs_visited)

是在嵌套調用的返回值結束。你不會把這個值賦給任何變量，所以python會在它進入下一次迭代時忘記它。你應該得到（幾乎）輸出作爲您已經使用下面的print語句，上面印着什麼相同：

for n in new_nodes: 
    ret = dfs(graph,n,dfs_visited) 
    print(ret)

（唯一的例外是通過你的初始呼叫，這將不被打印返回的值，從而應該有一個比以上少[0, 1, 2]行。）

來源

2017-08-10 08:16:00 nengel

感謝您的答案。我其實有一個後續問題。所以我也嘗試將遞歸調用分配給dfs_visited本身，並且該函數的行爲方式完全相同。那麼這裏發生了什麼？之前的dfs_visited變量以前的行爲幾乎就像一個全局變量，所以爲什麼不在循環的每次迭代中更新變量並不重要？ – user4505419

這並不重要，因爲您只創建單個列表對象（在原始調用中使用[]時），然後傳遞對它的引用。因此，在你的代碼中所有提到的'dfs_visited'都指向同一個容器 - 爲變量'dfs_visited'分配返回值（'dfs_visited'）將替換指針。 – nengel

遞歸DFS函數的中間結果 - Python

回答

相關問題