depth-first graph search that returns path to goal

python search recursion graph depth-first-search
mikey555 picture mikey555 · Sep 11, 2011 · Viewed 16.3k times · Source

I've been trying this all week and cannot, for the life of me, figure it out.

I know that I need to have a helper function that will recurse and return pathSoFar. I can't seem to get my head around the recursion.

I'm so confused that I can't even formulate exactly what the problem is besides recursion.

Thanks for any help.

EDIT: OK, I'll clarify a little bit. One thing that confuses me is what path is returned when a node has no neighbors. The goal path may be returned first, but then, because the helper is still recursing, it can return a dead-end path. I guess I'm confused about backtracking.

Answer

Ray Toal picture Ray Toal · Sep 11, 2011

Wikipedia actually has some pretty good pseudocode for depth-first traversal. These traversal algorithms label all the nodes in the graph with the order they appear in a traversal. You instead want to immediately return the path to the goal when the goal is found.

So let's modify the Wikipedia algorithm:

( INCORRECT ALGORITHM DELETED WHICH THE OP COMMENTED ON CORRECTLY BELOW )

Here is a Python implementation:

g = {
    'A': ['B', 'C', 'D'],
    'B': ['C', 'E', 'F'],
    'C': ['A'],
    'D': ['B', 'F', 'G', 'H'],
    'E': ['G'],
    'F': ['A', 'F'],
    'G': ['H', 'I'],
    'H': [],
    'I': []
}

def DFS(g, v, goal, explored, path_so_far):
    """ Returns path from v to goal in g as a string (Hack) """
    explored.add(v)
    if v == goal: 
        return path_so_far + v
    for w in g[v]:
        if w not in explored:
            p = DFS(g, w, goal, explored, path_so_far + v)
            if p: 
                return p
    return ""

# Hack unit test
assert DFS(g, 'A', 'I', set(), "") == "ABEGI"
assert DFS(g, 'A', 'E', set(), "") == "ABE"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'A', 'M', set(), "") == ""
assert DFS(g, 'B', 'A', set(), "") == "BCA"
assert DFS(g, 'E', 'A', set(), "") == ""

The idea here is that you want to find, in graph g, the path from v to goal, given that you already have come along the path in path_so_far. path_so_far should actually end just before v.

If v is the goal, you can add v to the path so far and that's it.

Otherwise, you will need to explore all edges emanating from v that do not have already explored nodes on the other end of the edge. For each of these edges, you can search (recursively) using your path so far plus the current node. If there is no path to the goal from v you will return an empty path.

The nice thing is that you are using recursion to "automatically backtrack" because you are passing the augmented path into your recursive call.

Related questions

Is there a short contains function for lists?

I see people are using any to gather another list to see if an item exists in a list, but is there a quick way to just do?: if list.contains(myItem): # do something

Read More
Python list of dictionaries search

Assume I have this: [ {"name": "Tom", "age": 10}, {"name": "Mark", "age": 5}, {"name": "Pam", "age": 7} ] and by searching "Pam" as name, I want to retrieve the related dictionary: {name: "Pam", age: 7} How to achieve this ?

Read More
Find an element in a list of tuples

I have a list 'a' a= [(1,2),(1,4),(3,5),(5,7)] I need to find all the tuples for a particular number. say for 1 it will be result = [(1,2),(1,4)] How do I do that?

Read More