How can I find the actual path found by BFS?

Question

The problem I'm trying to solve concerns a tree of MRT system.

Each node can be connected to 4 points at most, which simplify thing by a lot. Here's my thought.

struct stop {
    int path, id;
    stop* a;
    stop* b;
    stop* c;
    stop* d;
};

I can write code to save all the information I need for BFS to search for all the points, but my main concern is that, even though BFS finds the point properly, how can I know its path?

BFS will search each level, and when one of it reaches my destination, it will jump out of the run loop, and then, I will get a visited queue and an unvisited queue, how am i supposed to tell the user what stops he needs to visit when the visited queue is filled with every nodes BFS has searched?

Solution

To do so, you need to store a map:V->V (from vertices to vertices), which will map from each node v, the vertex u that "discovered" v.

You will populate this map during the iterations of BFS.

Later - you can reconstruct the path by simply going from the target node (in the map) up until you get back to the source, which will be your path (reversed, of course).

Note that this map can be implemented as an array if you enumerate the vertices.

Comments

[bewithaman]

Hey, what if I have to keep track of multiple paths of some length?

[amit]

@bewithaman That's a significantly harder problem. Finding if there is a path of length k for some k is NP-Hard problem (there is no known polynomial solution for it)