-1

我在 python 中有一个深度优先搜索示例代码，如下所示。

def DFS_paths_recursive(self, start, end, path = None):
    if path == None:
        path = [start]
    if start == end:
        yield path
    else:
        unvisited = set(self._graph_dic[start]) - set(path)
        for vertex in unvisited:
            yield from self.DFS_paths_recursive(vertex, end, path+[vertex])

但是如果我修改如下代码，输出很奇怪。我所做的只是在最后一行的递归调用之前修改路径。问题是什么？

def DFS_paths_recursive(self, start, end, path = None):
    if path == None:
        path = [start]
    if start == end:
        yield path
    else:
        unvisited = set(self._graph_dic[start]) - set(path)
        for vertex in unvisited:
            path.append(vertex)
            yield from self.DFS_paths_recursive(vertex, end, path)

例如，对于图，g = { "a" : ["d"], "b" : ["c"], "c" : ["b", "c", "d", "e"], "d" : ["a", "c", "e"], "e" : ["c"], "f" : ["g"], "g" : ["f"] } 有时“a”和“e”之间的路径输出为['a', 'd', 'c', 'b', 'e'],['a', 'd', 'c', 'b', 'e', 'e']，有时输出变为['a', 'd', 'e']。

4

1 回答 1

0

这与yield from. 当你这样做时path.append(vertex)，你改变了原始副本path（这意味着你的调用者传递给你的版本，以及你传递给递归调用的版本）。即使在函数中，它的行为也有所不同，因为重复append的 s 意味着每个递归调用都处理与最后一个相同的值再加一个，而不是固定基数path加上每个循环上的单个附加值。

做path+[vertex]的是创建一个新list的传递给递归调用，防止突变影响你自己的副本path，并且只为每个递归调用添加一个新value的到基础path而不改变基础path。

于 2015-10-23T03:59:10.950 回答