Search in depth of the first graph, returning the path to the goal

Question

I tried this all week and cannot, for me, understand this.

I know that I need a helper function that will return and return pathSoFar. I can't seem to plunge into recursion.

I am so confused that I can’t even formulate what the problem is, except for recursion.

Thanks for any help.

EDIT: Okay, I will clarify a bit. The only thing that bothers me is that the path returns when the node has no neighbors. The target path can be returned first, but then, since the helper is still recursive, it can return a dead end path. I guess I'm confused about the return.

Answer 1

Wikipedia does have some pretty good pseudo-code for circumvention. These crawl algorithms place all nodes in the graph with the order in which they appear in the crawl. Instead, you want to immediately return the path to the target when the target is found.

So, change 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 the path from v to goal in column g , given that you have already entered the path in path_so_far . path_so_far should end just before v .

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

Otherwise, you will need to examine all the edges emanating from v that have not yet explored the nodes at 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.

It's good that you use recursion to "automatically return" because you pass the extended path to your recursive call.

Answer 2

Recursion is the reduction of a problem to many smaller problems.

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

Now you have three subtasks: finding a route from B to Z, from C to Z and from D to Z. If you can solve any of these problems, you also solved the larger problem of finding a route from A to Z.

So you recurs. You use your findPath method on B, C and D, providing each with a list of the list of nodes visited so far containing A (so that they do not go back) [1]. If any of them says "I found a path," you take the path that they return, insert A at the beginning of it and name it day.

In recursive calls, you will end up in a node that is a neighbor of Z (if A and Z are actually connected). When this happens, you have solved the problem: return this link. If you find yourself in a node deadlock where every neighbor has already been visited, return a code that allows your subscriber to know it in the deadlock, and they should not use this node to try to build a solution.

[1] Note: if you are even smarter, you will also put B in the list that you pass to the recursive call to C, and B + C in the list that you go to D.