递归 DFS 函数的中间结果 - Python

Question

我基本上是想通过这个例子更好地理解递归。让我们看看下面的 DFS 算法，returns 所有节点都连接到基本根节点。本例中的 "graph" 被定义为顶点之间边的元组列表。

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]

在这种情况下，我很好奇的是，这是 "return" 仅来自一个递归调用的结果。显然，代码按照我预期的方式工作，我对结果很好，但我只是好奇中间 "returns" 的去向。例如，当我们运行在 return 语句之前添加打印语句的相同函数时，我们得到以下输出：

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 如何知道其中哪一个是函数的实际输出？是最后一个吗？

Answer 1

在递归调用函数的这一行中：

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

是嵌套调用的 return 值结束的地方。您不会将此值分配给任何变量，因此 python 会在它进入下一次迭代时立即忘记它。使用以下打印语句，您应该（几乎）获得与上面打印的相同的输出：

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

（例外情况是您最初调用的 return 值，不会打印出来。因此您应该比上面少一行 [0, 1, 2]。）

递归 DFS 函数的中间结果 - Python

Intermediate results in a recursive DFS function - Python

python

recursion

depth-first-search