我在 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']
。