我如何解释这个回溯代码？

Question

我很难理解回溯代码。特别是，我知道当我们找不到解决方案时，我们总是探索和回溯，但我不明白 path.pop() 行背后的逻辑。

我知道我们必须在探索后弹出元素，但这如何弹出正确的元素？

在此之前，我们可能会一直递归到子节点

# If current vertex is not destination #Recur for all the vertices adjacent to this vertex for i in self.graph[u]: if visited[i]==False: self.printAllPathsUtil(i, d, visited, path) 那么我们如何保证 path.pop() 删除 u 而不是其他节点？当我画出递归树时很有意义，但是有没有更容易理解的方法？

   '''A recursive function to print all paths from 'u' to 'd'. 
    visited[] keeps track of vertices in current path. 
    path[] stores actual vertices and path_index is current 
    index in path[]'''
    def printAllPathsUtil(self, u, d, visited, path): 

        # Mark the current node as visited and store in path 
        visited[u]= True
        path.append(u) 

        # If current vertex is same as destination, then print 
        # current path[] 
        if u ==d: 
            print path 
        else: 
            # If current vertex is not destination 
            #Recur for all the vertices adjacent to this vertex 
            for i in self.graph[u]: 
                if visited[i]==False: 
                    self.printAllPathsUtil(i, d, visited, path) 

        # Remove current vertex from path[] and mark it as unvisited 
        path.pop() 
        visited[u]= False


    # Prints all paths from 's' to 'd' 
    def printAllPaths(self,s, d): 

        # Mark all the vertices as not visited 
        visited =[False]*(self.V) 

        # Create an array to store paths 
        path = [] 

        # Call the recursive helper function to print all paths 
        self.printAllPathsUtil(s, d,visited, path)

Answer 1

printAllPathsUtil 每次调用都会收到一个指向当前 path 对象的指针。对 printAllPathsUtil 的新调用始终基于迄今为止的路径未探索且有效的基础。如果递归函数发现，它已经到达目的地 d，那么它会打印出完整的当前路径并后退一步，即路径的最后一个顶点被切断，算法会尝试寻找替代方案d 的路径（假设你的图没有重复的顶点，那么它必须是一个有 1 个以上顶点的 "detour"）。否则，尚未到达 d，您将继续探索所有从 u 出去但不在 path 的顶点（因此您不会返回您来自的地方）。这一直持续到所有可能的路径离开你的初始 s 已经被测试。

在整个过程中，path 仅在可能进行更多递归时才扩展并且修剪以便回溯到更早的状态。换句话说，您通过图形执行 depth-first-search，在每个顶点后分支（即使只有 1 个）。该算法总是先穷尽所有可能的路径，然后再回溯，因此 append-ing 和 pop-ing 是跟踪进度的正确方法。

我如何解释这个回溯代码？

How do I interpret this backtracking code?

recursive-backtracking