depth-first graph search that returns path to goal

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 co开发者_Python百科nfused about backtracking.

---

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.

---

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.