Suppose that there are two possible solutions—nodes d and e. In this case, e is the optimal solution, because it has the shortest path from root node a. Here, DFS finds the sub-optimal solution, d, before it finds the optimal solution, e. BFS finds the optimal solution, e, before it encounters node d:
Figure 19
We already saw that DFS uses less memory than BFS, and BFS finds the optimal solution. So, the choice of algorithm depends on how big the search space is (in this case, you will go for DFS), and whether finding the optimal solution is important (in this case, BFS is preferred).
Next, we will look at an application that ...
