20.4.3. Reconstructing Paths in BFS

In graphs, the input size is typically taken to be m and n. In other words, both parameters are somewhat independent of each other; because we could have the set of vertices could very few edges with very many edges.

This part introduces the concept of input size in graphs, denoting m as the number of edges and n as the number of vertices. It emphasizes that both parameters can vary independently, meaning a graph can have many vertices but very few connections (edges) or vice versa.

Think of it like a city map: you can have a lot of places (vertices), but if there are only a few roads (edges) connecting them, most places might remain isolated. Conversely, a small town could have lots of connections among a few landmarks.

So, how do we identify, how to go from the source vertex to a given vertex? 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.

This chunk discusses how, during the execution of BFS, you can discover whether one vertex (i) is connected to another (j). However, the process does not inherently keep track of the specific path taken to get to vertex j from vertex i, which is important if you want to reconstruct the entire route.

Imagine you're following a trail in a park. You may know that Trail A leads to a landmark, but you might not remember the specific path you took if there were multiple ways to reach that landmark from various starting points.

So, we can say that k was marked by i j, we will use the word parent. So, we will say that the parent of k is j, when following the parent links; we can reconstruct the path backwards from k to the original source vertex.

This chunk introduces the concept of 'parent' nodes in BFS. When a vertex k is visited for the first time from vertex j, we can keep track of this connection. By doing so, we can effectively remember how we arrived at k from j, and by tracing backwards, we can reconstruct the entire path from the target vertex back to the source vertex.

It’s like following a series of breadcrumbs left on a hiking trail. Each breadcrumb (parent node) shows you where you got to the next spot (current vertex), allowing you to trace your steps back to the starting point whenever you need.

This is very easy to do in our code. We just have to add one line, so we two lines. Initially, we say that for every vertex the parent is undefined. So, we had said a value like minus 1.

Here, the text discusses how to implement path reconstruction in the BFS algorithm. Initially, all vertex parents are set to an undefined state (like -1). As each vertex is explored, we then update the parent information accordingly, ensuring we record how each vertex was reached.

This is similar to writing down the names of every person you meet while visiting friends at a gathering. If someone asks you how you got to a particular friend's house, you can trace back to each person who guided you there.

Another thing that we can do in breadth-first search is keep track of the level. We said that the breadth-first search actually explores the graph level by level.

In this portion, the text explains that alongside tracking parents, BFS can also keep tabs on the 'level' of each node. The 'level' indicates how far away a vertex is from the source vertex in terms of the number of edges traversed. This additional information can help determine the shortest path in an unweighted graph.

Picture climbing a staircase, where each step up represents moving further away from the ground floor. The stairs are the edges, and your current floor level indicates how many edges you’ve crossed to get there.

Whenever we visit a new vertex, if it is level, if it is visited, then it must have a level. So, if level j is assign some number p, it must be t steps away from the original vertex.

This part elaborates on reinforcing the earlier concepts where, not only do we track how we got to each vertex (parent), but we also establish how many edges it took from the source to each vertex by updating its level. Combining both allows us to understand both the pathway and distance.

Think of navigating a city. If you have a map (tracking parents) and you also count how many blocks you travel (tracking levels), you can describe not only how to reach your destination but also how far it is from your starting point.

So now, we can trace a pair. So, we can say that, I got from 10, I came from 9, so 9 came from 8, so 8 came from 4, 4 came from 1.

In this final chunk, the explanation walks through an example of how to reconstruct the entire path using the collected parent information and level details. By following the parent links, you can create the complete path from the destination vertex back to the source.

It’s like retracing your steps after a walk to find out how far you went and to whom you talked. If you visited multiple friends on the way to your final stop, you can list them one by one to recreate your journey.

--