Depth First Search

• DFS is more than a furniture store.
• The idea is that, thinking of the space as a tree, you descend a branch, then backtrack and catch the other options.
• You can do this with a stack. You put you're current place on the stack, and you include the options.
• You choose one of the options (putting it on the stack), then recursively repeat.
• If you get to the goal, just read off the stack.
• If you get to a deadend, you pop the stack and choose another option from the stack.
• 
• Let's try it.
• Note that you have to mark cycles so that this terminates.