How can I find the actual path found by BFS?

c++ algorithm path breadth-first-search
Shane Hsu picture Shane Hsu · Mar 6, 2012 · Viewed 16.3k times · Source

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?

Answer

amit picture amit · Mar 6, 2012

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.

Related questions

How to replace all occurrences of a character in string?

What is the effective way to replace all occurrences of a character with another character in std::string?

Read More
What is the most effective way for float and double comparison?

What would be the most efficient way to compare two double or two float values? Simply doing this is not correct: bool CompareDoubles1 (double A, double B) { return A == B; } But something like: bool CompareDoubles2 (double A, double B) { diff = …

Read More
Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More