20.4.1. Tracking Parent Vertices

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.

In a breadth-first search (BFS), we explore a graph starting from a source vertex and mark each visited vertex. However, while we know which vertices are reachable from the starting vertex, we do not inherently know the sequence of vertices we traversed to reach any particular vertex. Hence, we need to track the path taken to get to each vertex from the source. This is achieved by storing parent information for each visited vertex.

Imagine you're guiding a friend through a maze. You both start at the entrance. As you navigate the paths, you keep a mental note of where you've been (the path taken) and which paths lead back to which turns (parent links). If asked later how to get back to a specific point, you can retrace your steps by following this mental map.

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, 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. By following the parent links, we can reconstruct the path backwards from k to the original source vertex.

To implement parent tracking, we maintain an additional array called 'parent'. Each time we visit a new vertex (let's call it vertex k) from its neighbor (let's call it vertex j), we set the parent of k to j. This way, whenever we mark a vertex as visited, we also note where it came from. Later, if we need to find out how to get back to the source from vertex k, we can keep following the parent links until we reach the original starting vertex.

Think about taking notes during a class. If your teacher introduces a concept (vertex k) using a previous topic (vertex j) as a reference, you write down that reference. Later, if you want to understand the new concept again, you can look back at your notes and trace back through the topics you've studied.

So, we can go backward because k was marked by j, j would be marked by some other thing and so on. By following these links back, we can go back from any k to this path vertex and therefore, we can reconstruct the path. The other thing that we can do in breadth first search is keep track of the level.

After establishing parent links, we can easily reconstruct the entire path from any vertex back to the source. By starting from the target vertex and following its parent pointers back to the source, we can trace the exact sequence of vertices that comprise the path. Additionally, while tracking parents, we can also maintain the 'level' of each vertex, indicating how far each vertex is from the source.

Imagine a family tree where each child knows who their parent is. If you want to trace your ancestry, you can start from yourself and keep going back through each generation (following parent links) until you reach the earliest ancestor. Similarly, in BFS, we can reconstruct the path taken through the graph using parent links.

So, remember, we said the breadth first search actually explores the graph level by level. 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 addition to tracking parents, we can also track at what 'level' we visit each vertex. The level indicates how many edges away a vertex is from the source vertex. For example, the source vertex is at level 0, its direct neighbors are at level 1, and so forth. This helps us understand not only if a vertex is reachable from the source but also how far away it is in terms of edges.

Think of a multi-story building. If you start from the ground floor (level 0), the first floor above you is level 1, the second floor is level 2, and so on. Similarly, in BFS, each vertex's level corresponds to its distance in terms of edges from the starting vertex.

--