How to build a BFS tree after running BFS on an undirected graph?

Question

I have an undirected graph and from it, I redrew the same graph but in a tree-like structure (with levels). I know how the Breadth First Search (BFS) algorithm works, but I am not sure how to do the transitioning from graph --> tree.

Here, in this Wikipedia article, if you scroll down a tiny bit, you'll see the two pictures of German cities. Even after reading the pseduo code on there, I just don't understand how you get from the first picture to the second.

Answer 1

One standard way to get a BFS tree from a graph is to run BFS and, as you do so, keep a table mapping each node in the graph to its parent in the tree. You populate it as follows: the source node has no parent (it's the root, after all). Then, whenever you're processing a node u and explore one of its unexplored neighbors v, you set v's parent to be u. Try tracing this out on some small examples and you'll see that this implicitly builds up the tree, except with the edges going backwards (edges point from children up to parents rather than the other way around). You can then just reverse the edges to get back the BFS tree.

Hope this helps!