1

I'm having trouble figuring out how exactly to get this to work... I'm attempting to get the shortest path to the goal using a DFS. I know that BFS is better but I was asked to use DFS for this. As you can see, I attempt to make a comparison between all stacks that lead to the end to find the goal, but it does not work, only the first stack that leads to the goal is ever printed... I know somewhere I need to unvisit nodes, but I cannot figure out exactly how. Right now I do get a path to the goal, but not the shortest one. Any help with this would be greatly appreciated.

false
  • 10,264
  • 13
  • 101
  • 209
seanscal
  • 568
  • 2
  • 9
  • 33

1 Answers1

3

Writing a non-recursive DFS is possible by using your own stack, but I find the recursive solution to be more elegant. Here is a sketch of one:

DFS(vertex)

    path.push_back(vertex)
    visited[vertex] = true

    if we found the exit
        output path
    else
        for each neighbor v of vertex
            if not visited[v]
                DFS(v)

    visited[vertex] = false
    path.pop_back()
  • this helped me so much i got it done based off this model. Thank you so much this makes a lot more sense and is a lot less code than what I was attempting – seanscal Mar 31 '14 at 16:18
  • It'd be a good exercise to write a non-recursive version, once you got your recursive version working. An advantage is that you take stack overflow out of the equation (no pun intended!) and you have some more flexibility to look at the current state, or if you wanted to make some changes to the algorithm. – M.M Mar 31 '14 at 22:54