CODEWITHSUNDEEP
recursive-backtracking
Kashif
Kashif

Reputation: 3327

How do I interpret this backtracking code?

I'm having a hard time understanding backtracking code. In particular, I know we always explore and backtrack when we don't find a solution, but I don't understand the logic behind the path.pop() line.

I know we must pop elements after exploration, but how does this pop off the right element?

Before that, we may recurse all the way down to the children nodes

# 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) so how do we guarantee path.pop() removes u and not some other node? It makes sense when I draw out a recursion tree but is there an easier way to understand this?

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

Upvotes: 0

Views: 117

Answers (1)

Xavier Mol
Xavier Mol

Reputation: 132

printAllPathsUtil receives a pointer to your current path object with every call. New calls to printAllPathsUtil are always made on the basis that the path so far is unexplored and valid. If the recursive function finds, that it has reached the destination d, then it prints out the complete current path and takes a step back, i.e. the last vertice of your path is cut off and the algorithm tries to find an alternative path to d (which then must be a "detour" with more than 1 vertices, assuming your graph has no duplicate vertices). Otherwise, d is not reached yet and you continue exploring all vertices going out of u, that are not in path already (so you don't go back where you came from). This goes on until all possible paths going out of your initial s have been tested.

Throughout that process, path was only extended whenever more recursion was possible and trimmed in order to backtrack to earlier states. In other words, you perform a depth-first-search through your graph, branching after every vertice (even if there's only 1). The algorithm always first exhausts all possible paths, before it backtracks, thus append-ing and pop-ing are correct methods to keep track of your progress.

Upvotes: 1

Related Questions