Depth First Search

• Here's a lab from BIS 2040 . How do you represent the maze in a graph?
• How do you get from the start state to the goal?
• One way is to do depth first search.
• Start at the start node, then choose a new connected state.
• Repeat this until you get to the goal.
• The problem is loops (when you return to a state).
• You can fix this by marking and back-tracking.
• DFS is a simple undirected search.