title: Why is my Depth First Search Implementation Broken
body: <p>I've been experimenting with different ways of implementing depth first search. I've found a few working ways, but they involved some rather tedious dictionary work. I've developed a new idea using lists, but the actions this implementation returns don't match the desired result. I'll try to comment the code as clearly as I can: </p>
  
  <pre><code>start = problem.getStartState()            ## returns an (x, y) tuple
  children = problem.getSuccessors(start)    ##returns the children of a parent node in ((start                  
                                             state), action, cost) format. 
  stack = Stack()                            ##creates a Stack (LIFO) data structure
  visited = []                               ##list of visited nodes
  visited.append(start)
  for child in children:
      stack.push((child, [], [], 0))         ##push children to fringe in the format of (child,
      while stack:                           ##path taken, actions taken, cost) 
          parent = stack.pop()
          node = parent[0]
          if parent[0] in visited: continue
          visited.append(parent[0])
          path = parent[1] + [node[0]]           ##assigns previous path/actions/cost to new 
          actions = parent[2] + [node[1]]        ##node, creating a cumulative, ordered list of
          print actions                          ##the path/actions and a cumulative cost
          cost = parent[3] + node[2]
          if problem.isGoalState(node[0]):
              print parent[2]
              return parent[2]                    ## returns list of actions 
          children = problem.getSuccessors(node[0])
          if children != []:
              for child in children:
                  stack.push((child, path, actions, cost))   ##assigns cumulative lists to child
  </code></pre>
  
  <p>Anyone see where my problems might lie in this implementation? BTW, I know DFS is an inefficient algorithm for most cases. But once I get this implementation right, it should be able to cross over to other search algorithms by simply changing the data structure that stores the children of the parent node. </p>