# Breadth-first traversal: difference between generation and expansion

The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names.

Some ground-rules: we're traversing in alphabetical order. And traversal must stop once the goal node has been generated, not expanded. This last part is where I feel like I'm not completely understanding what is being asked.

So the solution given is: Arad, Sibiu, Timisoara, Zerind, Fagaras, Bucharest.

What I think the solution is as follows: we're at A so A has been "generated". And then we expand A, giving us: A, S, T, Z. Since the goal node hasn't been generated we start with S. Expanding S gives us F and R (no goal node yet) and then we expand T giving us L following which Z is expanded giving us O. So far we have A, S, T, Z, F, R, L, O. Now, going alphabetically, we go to F for expansion. This gives us B and this is where the traversal should stop.

So my solution is A, S, T, Z, F, R, L, O, B.

Can you tell me where I'm going wrong and why the given solution (as opposed to my solution) is correct?

• I’m confused since neither solution seems like a path from A to B. For example there is no edge from S to T. – Throckmorton Aug 18 '19 at 6:37
• I actually figured it out. The given solution is correct because it's the order in which the nodes are expanded, not the actual solution of the path. – investigate311 Aug 19 '19 at 7:23