CODEWITHSUNDEEP
pythonalgorithmrecursiongraphdepth-first-search
Sam
Sam

Reputation: 55

Depth first search to find path in graph

I am trying to find a path between two points in a graph using a depth first search in Python. The idea is to return a path (not necessarily the shortest) from point a to point b or an empty list if a path does not exist. I have a class which contains an adjacency list (dictionary called graph), a dictionary of visited nodes and a stack (a list called path) to track the current path. The recursive function I am using to do this is a method called getPath(self,a,b). The issue I am having is that I am unable to return the stack once I have found the target node, I think because the stack is just returned as part of a recursive call and the function continues running. What can I change to make this work? The code is as follows:

def getPath(self,a,b):
        self.visited["{}".format(a)]=1 #mark a as visited
        self.path.append("{}".format(a)) #add a to current path
        if ("{}".format(a)=="{}".format(b)): #check to see if we've reached our destination
            return self.path #here is where I would like the function to return the path
        else:
            for v in self.graph["{}".format(a)]:
                if self.visited[v]==0:
                    self.getPath(v,b)
            self.path.pop #remove v from our current path if we only find dead ends from its edges

Upvotes: 0

Views: 1378

Answers (1)

Yash Shah
Yash Shah

Reputation: 1654

In the above code in the else block, you are returning nothing for the recursive call.

So, what if the children call:

self.getPath(v,b)

returns self.path but in the parent call of that function gonna return nothing.

So, you have to make some changes in the else block to keep track of these return values.

def getPath(self,a,b):
        self.visited["{}".format(a)]=1 #mark a as visited
        self.path.append("{}".format(a)) #add a to current path
        if ("{}".format(a)=="{}".format(b)): #check to see if we've reached our destination
            return self.path #here is where I would like the function to return the path
        else:
            for v in self.graph["{}".format(a)]:
                if self.visited[v]==0:
                    result = self.getPath(v,b)
                    if(result != None):
                        return result
            self.path.pop #remove v from our current path if we only find dead ends from its edges
            return None

Upvotes: 1

Related Questions