Exam-style question
Try this first
A depth-first search is used to navigate a maze. From S, the available routes are considered in this order: S connects to A and B; A connects to C; C connects to D; D is a dead end; B connects to E; E connects to G. Trace the order of first visits until G is reached, including the backtracking that is needed.
Model answer
What a good answer should say
- The first-visit order is S, A, C, D, B, E, G.
- The search follows S-A-C-D, reaches the dead end D, backtracks to C, then A and S, and takes the untried route S-B-E-G.
Explanation
Why this works
Depth-first search follows the first route as far as it can. After reaching D, there is no unvisited continuation, so it backtracks through C and A to S.
It then explores B, followed by E, and reaches G.
Common mistake
No common mistake is linked to this question yet.