So I have a problem that I want to use depth first search to solve, returning the first path that DFS finds. Here is my (incomplete) DFS function:
start = problem.getStartState()
stack = Stack()
visited = 
parent = stack.pop()
if parent in visited: continue
children = problem.getSuccessors(parent)
for child in children:
You are right - you cannot simply return the stack, it indeed contains a lot of unvisited nodes.
However, by maintaining a map (dictionary):
map:Vertex->Vertex such that
parentMap[v] = the vertex we used to discover v, you can get your path.
The modification you will need to do is pretty much in the for loop:
for child in children: stack.push(child) parentMap[child] = parent #this line was added
Later on, when you found your target, you can get the path from the source to the target (pseudo code):
curr = target while (curr != None): print curr curr = parentMap[curr]
Note that the order will be reversed, it can be solved by pushing all elements to a stack and then print.
I once answered a similar (though not identical IMO) question regarding finding the actual path in BFS in this thread
Another solution is to use a recursive version of DFS rather then iterative+stack, and once a target is found, print all
current nodes in the recursion back up - but this solution requires a redesign of the algorithm to a recursive one.
P.S. Note that DFS might fail to find a path to the target (even if maintaining a
visited set) if the graph contains an infinite branch.
If you want a complete (always finds a solution if one exists) and optimal (finds shortest path) algorithm - you might want to use BFS or Iterative Deepening DFS or even A* Algorithm if you have some heuristic function