python - 在 python 中编写更好的递归深度优先搜索

Question

我正尝试在 python 中构建一个图形库(连同标准图形算法)。我已经尝试实现 DFS，这就是它的样子

def DFS(gr, s, path):
    """ Depth first search 
    Returns a list of nodes "findable" from s """
    if s in path: return False
    path.append(s)
    for each in gr.neighbors(s):
        if each not in path:
            DFS(gr, each, path)

这工作正常，但我对它的使用方式不满意。例如。目前你需要这样做

 path = []
 DFS(mygraph, "s", path)
 print path

取而代之的是，我希望以这种方式使用 DFS

path = DFS(mygraph, "s")
print path

使用递归 DFS，我无法想出像上面那样工作的实现。有人可以给我一些关于如何实现这一目标的指示吗？

Answer 1

只需创建一个包装器方法来调用您已有的方法:

def DFS(gr, s):
    path = []
    DFS2(gr, s, path)
    return path

此处 DFS2 是您在上面显示的方法。