I have an assignment involving Depth and Breadth first searching using stacks and queues respectively, and I think I have the search down for both, but I can't figure out how I'm supposed to then output/track the solution path; it seems all the intermediate steps are destroyed in the search. Just to be clear, the general algorithm I am using is:
Push start node
While(!Stack/Queue empty)
Pop top/front
If goal, return
Else push all successor nodes
For the DFS I came up with an algorithm that works, storing the solution path on a separate stack. However for the BFS I am lost, there seems to be too much to keep track of. I am using this on a non directed graph (using adjacency table) which represents a map with interconnected cities, so there are loops and multiple solutions; I don't need the best path, just a way to track the solution the algorithm found.
This is homework so I'm not asking for code or anything, just a qualitative description of how a solution can be tracked in BFS. Thank you for your time.