用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)

这很好，但我不满意它需要如何使用。E、 g.目前你需要这样做

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

相反，我希望以这种方式使用DFS

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

有了递归DFS，我无法想出像上面这样工作的实现。有人能给我一些关于我怎样才能做到这一点的建议吗？

Answer 1

实际上，为什么不将path设置为默认的空列表呢？ 因此，使用相同的代码，但参数略有不同：

# Original
def DFS(gr, s, path):

# Modified
def DFS(gr, s, path=[]):

# From here you can do
DFS(gr, s)

Answer 2

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

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

这里DFS2是您上面展示的方法。

Answer 3

根据chutsu的建议，您可以为访问的节点使用空的默认值，但是要小心使用mutable default arguments。 另外，我建议使用集合而不是列表来进行常量查找。

def DFS(gr, s, visited=None):
    """ Depth first search 
    Returns a list of nodes "findable" from s """
    if visited == None:
        visited = set([s])

    for each in gr.neighbors(s):
        if each not in visited:
            visited.add(each)
            DFS(gr, each, visited)

    return visited