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 = targetwhile (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

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']

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/