title: Tracing and Returning a Path in Depth First Search
body: <p>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:</p>
  
  <pre><code>    start = problem.getStartState()
      stack = Stack()
      visited = []
      stack.push(start)
      if problem.isGoalState(problem.getStartState):
          return something
      while stack:
          parent = stack.pop()
          if parent in visited: continue
          if problem.isGoalState(parent):
              return something
          visited.append(parent)
          children = problem.getSuccessors(parent)
          for child in children:
              stack.push(child[0])
  </code></pre>
  
  <p>The startState and goalState variables are simply a tuple of x, y coordinates. problem is a class with a variety of methods. The important ones here are getSuccessors (which returns the children of a given state in the form of a list of 3 item tuples. for this part of the problem though, only the first element of the tuple, (child[0]), which returns the state of the child in x, y coordinates, is important) and isGoalState (which provides the x, y coordinates of the goal state). </p>
  
  <p>So I THINK (difficult to test at this point), that this function, given proper implementation of everything else, will return once it has reached a goal state. Please let me know if I am missing something. My biggest issue, though, is WHAT to return. I want it to output a list of all of the states it takes to get to the goal state, in order from the beginning to the end. It doesn't seem like simply returning my stack will do the trick, since the stack will include many unvisited children. Nor will my visited list yield anything useful, since it is conceivable I could reach dead ends, have to backtrack, but still have the dead-end tuples in the visited list. How would I go about getting the list I desire? </p>