depth-first graph search that returns path to goal

Question

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.

Solution 1

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.

Solution 2

Recursion is about reducing a problem to a set of smaller problems.

In this case, let's say you are trying to find a route from node A to node Z. First you look at the neighbors of A. Let's say they are B, C, and D.

Now you have three sub-problems: finding a route from B to Z, C to Z, and D to Z. If you can solve any one of those problems, you have also solved the larger issue of finding a path from A to Z.

So, you recurse. You employ your findPath method on B, on C, and on D, giving each one a list of nodes-visited-so-far containing A (to prevent them from going backwards) [1]. If any of them says "I found a path", you take that path they return, stick A at the beginning of it, and call it a day.

In the recursive calls, eventually you will find yourself at a node which is a neighbor of Z (if A and Z are actually connected). When that happens, you have solved the problem: return that link. If you end up at a dead-end node where every neighbor has already been visited, return some code which lets your caller know it's a dead end and they shouldn't use that node to try to build a solution.

[1] Side note: if you're extra clever, you'll also put B in the list you pass to the recursive call on C, and B+C in the list you pass to D.

Comments

[mikey555]

how could you backtrack using this method, though?

[Ray Toal]

In reponse to your edit, a DFS on a node with no neighbors will return a path containing itself if it is the goal, and the empty path if it is not. Are you looking for an algorithm for DFS in any particular language?

[Borealid]

@Ray Toal: a recursive method is doing exactly what you describe, but using the operating system stack instead of an explicit in-application one. I wouldn't push a just-learning-CS programmer to use an explicit stack because, although it is more efficient, it requires more code to produce the same algorithm.

[Ray Toal]

@Boreald okay, I think you are right. The recursive solution does require less code.

[mikey555]

Is it possible to incorporate a stack into this method? I'd like to use a stack and return a path, but I'm thinking it's not possible. A node must be called directly by its parent to retain its path, since I can't let nodes have the property of the path behind them (it's a homework assignment). Using a stack would result in a node being evaluated in isolation, and I couldn't pass the path to the node's parent through to the node.

[mikey555]

hmm, I see a problem in the code above. The for-loop checks all the children of a node, but it will reach the return statement on the first unexplored node it sees, regardless of if that node is in the correct direction. It won't have a chance to check the other children. Am I wrong? My fix: for all children { if child is unvisited { pathToGoal = DFS( ... , pathSoFar + v); if pathToGoal is notNone { return PathToGoal; } } } return None

[Ray Toal]

@michael.greenwald hats off and many thanks for pointing this out! Writing pseudocode was a bad idea. I will spend some time tonight developing a real path finding app.

[Ray Toal]

@michael.greenwald Thanks again. I wrote an actual Python implementation that might be useful to you. One hack is that the accumulated path is a string as opposed to an array, but I think you can work with that. :) HTH.

[mikey555]

thanks for all the help man. i found the easiest way to do it: instead of putting the successor on the stack, just put the tuple (successor, pathSoFar) on the stack! it's a more memory-intensive solution, but it provides that path history.