How can I modify the breadth-first search algorithm to also include the solution path?

Question

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.

Answer 1

Set 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. Parent[root] is nil and the recursion will stop there.

Answer 2

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.

Answer 3

Look at http://stackoverflow.com/questions/1579399/shortest-path-fewest-nodes-for-unweighted-graph/1579508#1579508; I've implemented the correct solution, but it's in Java.