Consider a breadth-first graph search on the graph above (where S is the start and G is the goal state). Assume that ties are broken alphabetically (so S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A). You will probably find it easier to execute the search on a sheet of scratch paper rather than trying to think it through on the computer screen.

Enter the final path returned by depth-first graph search in the box below. Your answer should be a string of characters starting with S and ending with G. Don't include arrows or spaces. For example, if you believe the path is S->X->G, put SXG in the box.