我的递归函数有问题，希望在这里得到帮助。
我想编写一个函数，其中找到两个节点之间的所有路径，该函数应在找到解决方案后停止并输出第一条路径。如果已经找到该路径，则该函数应继续，直到找到下一条路径，然后再次停止并输出找到的路径。
为此，我编写了一个函数（或者我打算这样做），它从起始节点开始，然后到其邻居节点，然后到邻居节点的邻居节点，依此类推，直到到达结束节点。然后它应该输出路径。如果未到达结束节点，则应删除最后一个节点并从那里继续。所以一种带回溯的DFS算法。我的问题是该函数在找到结束节点后不会停止。我认为这是因为仍然有“打开”的功能需要关闭。如果我在代码底部写“return pathfind(nknots)”而不是仅“pathfind(nkots)”，那么我的代码在到达结束节点时停止，但如果尚未到达结束节点，则不会继续回溯。所以在这两种情况下我都有问题。
有人知道我如何解决这个问题吗？最好是我不必过多更改自己的代码/想法的方式？
def pathfind(x):
visited.add(x)
if neighbours[x] != {}:
for nknots in neighbours[x]:
if nknots == n:
print("final node is found")
augpath.append(n)
return augpath
elif nknots in augpath or nknots not in neighbours or nknots in visited:
print("Node already in augpath, visited or has no neighbours: ")
continue
else:
augpath.append(nknots)
pathfind(nknots) # pathfind on new node
visited.remove(nknots)
augpath.pop()
return
语句来告诉它停止：
def onepath(start, end, neighbours, path=[], visited=None):
if visited is None:
visited = {start}
if start == end:
return path + [start]
else:
for n in neighbours[start]:
if n not in visited:
visited.add(n)
p = onepath(n, end, neighbours, path + [start], visited)
if p:
return p
return None
如果你想找到所有路径，那么你应该返回一个由所有递归调用找到的所有路径组成的列表：
def allpaths1(start, end, neighbours, path=[], visited=set()):
if start == end:
return [path + [start]]
else:
return [p
for n in neighbours[start]
if n not in visited
for p in allpaths1(n, end, neighbours, path + [start], visited | {start})
]
请注意，使用双 for
进行列表理解的语法有点尴尬。对于这些类型的函数，我认为最Pythonic的方法是使用生成器，而不是列表：
def allpaths2(start, end, neighbours, path=[], visited=set()):
if start == end:
yield path + [start]
else:
for n in neighbours[start]:
if n not in visited:
yield from allpaths2(n, end, neighbours, path + [start], visited | {start})
neighbours = {1: [2, 3, 4], 2: [1, 3], 3: [1, 2, 4], 4: [1, 3]}
# 1 - 2
# | \ |
# 4 - 3
print(onepath(1, 3, neighbours))
# [1, 2, 3]
print(allpaths1(1, 3, neighbours))
# [[1, 2, 3], [1, 3], [1, 4, 3]]
print(list(allpaths2(1, 3, neighbours)))
# [[1, 2, 3], [1, 3], [1, 4, 3]]