找到解决方案后如何停止递归/return

Question

我的递归函数有问题，希望能在这里得到帮助。

我想写一个函数，找到两个节点之间的所有路径，函数应该在找到解决方案后停止并输出第一条路径。如果已经找到这条路径，函数应该继续，直到找到下一条路径并再次停止并输出找到的路径。

为此我写了一个函数（或者我打算），它从起始节点开始，然后到它的邻居节点，然后到邻居节点的邻居节点等等，直到到达结束节点。然后它应该输出路径。如果没有到达结束节点，它应该删除最后一个节点并在那里继续。所以一种带回溯的DFS算法。

我的问题是函数在找到结束节点后没有停止。我假设这是因为仍然有需要关闭的功能“打开”。如果我在代码底部写“return pathfind(nknots)”而不是“pathfind(nkots)”，那么我的代码会在到达结束节点时停止，但如果结束节点有，则不会继续回溯尚未达成。所以在这两种情况下我都有问题。

有没有人知道我该如何解决这个问题？最好是我不必过多改变自己的 code/idea ?

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

Answer 1

如果你想让函数一遇到结束节点就停止，return路径，那么你应该使用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

如果你想找到所有路径，那么你应该return一个由所有递归调用找到的所有路径组成的列表：

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]]

找到解决方案后如何停止递归/return

How to stop recursion after finding solution / return

python

recursion

return

graph