20.4.2. Tracking Levels

Now, 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 breadth-first search (BFS), we determine which vertices are connected to our starting point or source vertex. However, just knowing that two vertices are connected does not provide the specific pathway between them. For instance, if we start our search from vertex 'i' and mark vertex 'j' as visited, we understand that 'i' and 'j' are adjacent. The next logical step is to find out the exact route taken from 'i' to 'j'. This aspect is crucial for numerous applications, such as finding efficient routes in navigation systems or understanding social networks.

Think of this like navigating through a city using a map. You might discover that you can travel from your house (vertex 'i') to a friend’s house (vertex 'j') using several routes. While you know the two locations are connected, finding out the specific streets to take is essential for actually getting there.

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, when but following the parent links; we can re construct the path backwards from k to the original source vertex.

To keep track of the path derived from the BFS, we introduce the concept of 'parent links.' Whenever we visit a vertex 'k,' we record who first marked 'k' as visited, which is another vertex 'j.' We can then say that 'j' is the parent of 'k,' meaning that to arrive at 'k,' we first had to visit 'j.' By following these parent links back, we can reconstruct the entire path taken to reach 'k' from our source vertex. This is important in various algorithms, as it helps in backtracking and provides clarity in understanding the traversal.

Imagine retracing your steps after visiting a new restaurant in a city. You remember your journey by noting down which streets you took to reach the restaurant (each street being a 'parent' to the next). By recalling this route in reverse, you can easily find your way back home.

So, we can go backward, so because k was mark by j, j would be mark by some other thing and so on. So, by this 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. So, remember, we said the breadth first search actually explores the graph level by level.

While reconstructing paths through parent links is one way to enhance BFS, we also want to keep track of 'levels.' Each level represents how many steps away a vertex is from the starting vertex. Initially, every vertex's level is undefined. When we visit a new vertex for the first time, we assign its level as one more than the level of the vertex it was reached from. This approach not only helps identify connectivity but is especially beneficial in determining the shortest path in terms of edges between any two vertices.

Consider climbing a staircase. The first step you would take is from the ground to the first stair (level 0 to level 1). Each additional step you climb adds to your level. If someone asks you how high you are, you can easily tell them by counting how many stairs you've stepped on.

So, this can also be easily added to a code along with a parent code. So, last time, we added this assignment for the parent. Now, we also add the assignment for level, so we say initially the level of each vertex is undefined. So, it is some non sensible value like minus 1. When, we say that the level of the start vertex is 0, and now whenever we visit a new vertex, if it is level, if it is visited, then it must have a level.

To implement level tracking in our BFS code, we initialize a level array where every vertex starts with an undefined value (like -1). The source vertex is assigned a level of 0, indicating that it is at the starting point of our search. For every new vertex we visit, if it is being visited for the first time, we update its level to one more than the level of the vertex we just came from. This creates a clear hierarchy of levels in the graph that reflects the distances in terms of edges from the source.

Think of a tree where the root represents the starting point. Each branch represents the different levels or heights as you move away from the trunk. Each subsequent branch that extends from the original trunk can be seen as adding a level; thus, the tree's structure reflects the levels just as the graph does.

So, in graphs the input size is typically taken to the 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. So, usually m and n together are taken to be the input size. So, order m plus n is actually a linear algorithm.

In graph representations, the size parameters include the number of vertices (n) and the number of edges (m). These parameters are generally independent, indicating that a graph can have many vertices but very few edges and vice versa. The complexity of BFS is analyzed based on these two factors—the overall time complexity for the algorithm is primarily linear, O(m + n). This efficiency signifies that BFS can process large graphs effectively, especially when implemented with an adjacency list representation.

Consider a social network where users represent vertices and connections (friendships) represent edges. You could have many users (vertices) but very few actual connections (edges) between them due to the nature of relationships. Thus, measuring the size of a network is similar to understanding the relationship between vertices and edges in a graph.

--