Tracing and Returning a Path in Depth First Search

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[0])
        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

this link should help you alot ... It is a lengthy article that talks extensively about a DFS search that returns a path... and I feel it is better than any answer I or anyone else can post

http://www.python.org/doc/essays/graphs/

Not specific to your problem, but you can tweak this code and apply it to different scenarios, in fact, you can make the stack also hold the path.

Example:

     A
   /    \
  C      B
  \     / \
   \    D E
    \    /
       F
       

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    visited = set()
    while stack:
        (vertex, path) = stack.pop()
        if vertex not in visited:
            if vertex == goal:
                return path
            visited.add(vertex)
            for neighbor in graph[vertex]:
                stack.append((neighbor, path + [neighbor]))

print (dfs_paths(graph, 'A', 'F'))   #['A', 'B', 'E', 'F']