Trace the method isPathwith the map in Figure 6-10 for the following requests. Show the state of the stack after each step.

Question

a.Fly from A to B.
b.Fly from A to D.
c.Fly from C to G.

Answer 1

a.(Stack contents are listed from top to bottom.)
Push origin A onto stack and mark A as visited.
aStack: A topCity: A
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: B Push B onto stack and mark B as visited.
aStack: B A topCity: B
aStack is not empty and topCity is the destination, so the while loop exits.
aStack is not empty, so isPath returns true.
b.
Push origin A onto stack and mark A as visited.
aStack: A topCity: A
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: B Push B onto stack and mark B as visited.
aStack: B A topCity: B
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: D Push D onto stack and mark D as visited.
aStack: D B A topCity: D
aStack is not empty and topCity is the destination, so the while loop exits.
aStack is not empty, so isPath returns true.
c.
Push origin Conto stack and mark C as visited.
aStack: C topCity: C
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: D Push D onto stack and mark D as visited.
aStack: D C topCity: D
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: E Push E onto stack and mark E as visited.
aStack: E D C topCity: E
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: I Push I onto stack and mark I as visited.
aStack: I E D C topCity: I
aStack is not empty and topCity is not the destination, so the while loop exits.
nextCity: NO_CITY
Backtrack by popping the stack.
aStack: E D C topCity: E
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: NO_CITY
Backtrack by popping the stack.
aStack: D C topCity: D
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: F Push F onto stack and mark F as visited.
aStack: F D C topCity: F
aStack is not empty and topCity is not the destination, so the while loop continues.
nextCity: G Push G onto stack and mark G as visited.
aStack: G F D C topCity: G
aStack is not empty and topCity is the destination, so the while loop exits.
aStack is not empty, so isPath returns true.