Solution to part (a): Depth-first search

1. What is the final path found? s -> a -> b -> h -> i -> g.
2. How many nodes were expanded? 7.
3. Explain why it selected nodes during the search that were not on the shortest path from s to g. It selects nodes in order irrespective of where the goal is.
4. Explain why it may have been led astray in the final solution. It reports whatever path it finds first; this could be any path depending on the order of the neighbours.