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

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)