I have the following pseudo-code in my book for a breadth-first search:
function breadth_first_search: begin open := [Start] closed := ; while open !=  do begin remove leftmost state from open, call it X; if X is a goal then return SUCCESS else begin generate children of X; put X on closed; discard children of X if already on open or closed; put remaining children on right end of open; end end return FAIL; end
I've implemented a similar algorithm myself following these pseudo-code instructions. My question is, what is the simplest way to modify it so it maintains the solution path?
Simply knowing I can reach a solution isn't nearly as useful as having a list of transitions to get to the solution.
Is there any possibility for you to change the Tree structure? If so, you might want to add a
parent pointer in each node/leaf so when you find the solution you go up following parent pointers up to the root.
Parent[childNode] = currentNode as you enqueue each node (when you set
Visible[Node] = 1).
Then recursively look up the
Parent array, starting at the node you want and append each node you see in the
Parent array to the path.
nil and the recursion will stop there.