20.4. Path Reconstruction in BFS

So, we can do something more in breadth first search, all we have identified is which vertices are connected to the usual vertex one of the source vertex in general from where you start breadth first search. So, how do we identify, how to go from the source vertex for given vertex. So, if we started i and BFS i sets visited j equal to 1, we know that i and j are connected, but we do not know the path.

So, what we can easily do is to remember, where we marked each vertex from. So, when we mark a vertex k as visited, it is marked because it is a neighbor of some already visited neighbor j. So, when we can say that k was marked i j, we will use the word parent. So, we will say that the parent of k is j, when but following the parent links; we can reconstruct the path backwards from k to the original source vertex.

In Breadth First Search (BFS), we identify how connected nodes relate to each other. When we visit a vertex 'k', it is typically because we have moved from another vertex 'j'. By labeling the previous vertex as the 'parent' of the new vertex, we create a reference point from which we can trace the path from any vertex back to the source.

As we traverse the graph, we can construct a pathway by backtracking through these parent nodes. For instance, if we arrived at vertex '4' from '1' and later from '4' to '5', we can represent this relation as 'parent of 5 is 4', and 'parent of 4 is 1'. Hence, to recover the path taken from '1' to '5', we would go from '5' to '4', and then from '4' to '1'. This method not only shows the connected vertices but also how to navigate from any point back to the origin.

Imagine trying to find your way back home after visiting a friend. Each place you visit, you leave a breadcrumb (the parent) at each step. When you want to return, you can follow these breadcrumbs backwards to find your way home easily. Each breadcrumb gives you an instance of where you came from, allowing you to trace back to your origin.

So, the other thing that we can do in breadth first search is keep track of the level. So, remember, we said the breadth first search actually explores the graph level by level. Looks at all the vertices to the one step away from the source, then those vertices are one step away from these what, so there at level 2, two steps away from the source and so on.

So, instead of just saying that the vertex is visited, we can ask at what level it was visit. So, initially we say that all the levels are undefined, and then each time we visit a new vertex, it is 1 level more than the vertex from which it was visit.

In BFS, not only do we determine which vertices are connected, but we also categorize how far each one is located from the starting point, in terms of levels. Each vertex level indicates its distance from the source vertex. When we process a vertex, its level is determined by adding one to the level of the vertex we visited it from.

If the starting vertex is assigned level '0', the next vertices directly connected to it will be at level '1', the vertices directly connected to those will be at level '2', and so on. This hierarchical level assignment allows us to understand how many edges need to be crossed to reach any vertex from the starting vertex.

Think of the levels in BFS like a hierarchy of a company. At the top is the CEO (level 0), and anyone directly reporting to them (like managers) is at level 1. Those who report to managers (like employees) are at level 2, and so forth. If you want to know how far someone is in the company hierarchy, you just count the number of levels down from the CEO.

So, we can see all this works in our earlier example, as usual we start with 1 and we mark it is level as 0 and it does not have a pair. Now, when we add 2, 3 and 4 all of them will be at level 1 and all of them will have that is parent 1, because we have an explore from 1. Then, as before two does not add anything new to our list, p does not add anything to a list.

Now, 4 will add 5 and int, so far these 2, the level will be 2 and the parent will be 4, indicating that I bought to 5 and 8 from 4 in my exploration. Then, from 5, I will get 6 and 7. So, these are now at level 3, because 5 was itself at level 2, therefore, 6 and 7 are at level 3 and their parents are 5, from 8, I will go to 9, a 9 is also at level 3, because 8 was already at level 2, so 9 is level 3 and it is parent to the 8.

In practice, BFS not only tracks which nodes are connected but also records their levels and how they connect back to their parents to reconstruct paths effectively. By starting from the root node (let’s say vertex '1', level '0'), we can see how other nodes are added step-by-step. For instance, if '2', '3', and '4' are directly connected to '1', they will be at level '1' with '1' as their parent. Continuing this method, we can deduce who connects to whom, their hierarchical levels, and trace back the exact path that led us from the starting node to any other node in the graph.

Imagine climbing a mountain where the starting point is the base camp (level 0). As you reach each camp higher up (levels 1, 2, 3), you take note of which camp you left from (your parent). By the time you reach the summit, if someone asks how you got there, you could trace back your steps from the peak down to the base camp, explaining which camps you stayed at on the way up.

--