Okay, so we have seen that to, to computer distances in the graph, we can go in, proceed in layers. To proceed in layers and deal with this node first, then this node, these nodes seconds, then these nodes, we needed to use a data structure that we called a queue. Again, a queue is a, is a, think about as a list that has two end points, one is called the head, one is called the tail. That when we put things or the operation we call is in queue, when we want to put an element x on the queue. Suppose this queue is called Q, we have an operation that's called enqueue where we add an element x to the queue. It is implicit that x is going to be at the tail of the Q, okay? And when we want to process a node when I say it is time now to compute the distances to all the neighbors of 1, then we have to get 1 out of the queue and this for that we use an operation called dequeue, and then we just justify the Q because. You cannot access the queue in any way you want. When you say, I want an element from the queue, you will always get the element that's at the head of the queue. Okay? So you, equipped with this data structure of queue, and with these two operations, all the, the only operations we need on the queue. Now, we can actually implement this algorithm, or think about writing this algorithm formally, in a clean way. And the way the algorithm will proceed is that first, we will put only node 0 in the queue, right, because it is the original node or the source node from which we are computing these answers. We will put node 0 in the queue, then, after that, we will say, okay, let's look at all the neighbors of node 0, that, whose distances haven't been computed yet. For each one of them we will update its distance by adding, by saying that d1 is d0 plus one. We will compute the distance to this, and compute distance to this, and for each one of them, when we compute its distance, we immediately put it on the queue. So we say, d1 equal 1, put 1 on the queue. D3 equal 1, put 3 on the queue. D4 equal 1, put note 4 on the queue. Once we are done with this, 0 is already removed from the queue because we have dealt with it. Now the queue is going to have three elements in it, 1, 3, and 4. Then we say, ok, lets process things that are in the que. We take node 1 from the que, process it, now one is removed from the que. We deal with all it's neighbors, when we are dealing with them, since 0 and 3 have been dealt with, neighbor 2 hasn't been dealt with, we add 2 to the que, so now the que does, has only 3, then 4, then 2. And so on, okay. So this is a clean way of keeping track of which nodes have been, have been processed, distances to them have been computed, which nodes we still have to process, okay. So it's very important to emphasize the significance of data structures. In this case we needed this data structure of a Q. I could have used a set, a set to put these notes in. However a set is an un-ordered collection of items. It's not going to, we're not going to be able to keep track in a set of which node was processed first. Which node was processed second and so on. Okay? So the choice of a data structure is crucial for the algorithm. And sometimes multiple data structures can work, however, the choice of the data structure, even among ones at work, might affect the running time of the algorithm. So it's very important to keep in mind that consideration, that data structures play a crucial role in the running time, or dictate the running time of the algorithm. So, here in this algorithm, in BFS, we have seen one of the first data structures in this course, which is called a queue, and it is crucial for this algorithm. So every time you want to maintain a list of items, in the same way you would, you can think of a queue in a cafeteria, or at the bank, or in a hospital, for example. This is how you would, this is the type of instructions that you would use, okay? So, now that we have, we are equipped with this data structure of queue,, now we know how to deal with, with, with, the, the graph in layers. We have just to pay attention to a few more, to a few more details. The first of which. As actually has already occurred here, is that when I'm computing the, the dist, I compute the distance to node one and d one equals one and then next time I say okay, let me now look at all the neighbors of one and suppose now I'm looking at this neighbor three. If I say the distance to three is the distance from zero to one plus one, I'm going to get a distance of two. However, we have already visited node three through our much shorter path of distance one. So it is very important when we are dealing and with this algorithm that when we check the neighbors of a node, before we update its distance or before we say here's the distance to this node, the first thing we need to check is if the distance has been computed. Okay? If the distance has been computed. So how would we do this in an algorithm? That, one of that, the, the common ways to, to handle this kind of case is to see, has the distance been computed? Is, before we do anything in the algorithm, the first step we do, we initialize the distances to all nodes. We initialize every dj. Initialize every, for every j in V, for every node, we initialize dj to infinity. Okay? So this will be the first step, saying that the distance from node i to every node is infinity, okay? Including to i itself. Then, after that. When we come to handle, when we come to handle a neighbor un, the first thing we need to check is the j still infinity. So in this case, when I am computing the distance to, to node three coming from one, I will, the first question I will ask, is d three infinity? If d three is infinity, it means that we have not visited it through any other path. Which means it is time to update its distance to some finite number. However, in this case, when I come from node one to node three, I saw what is d3? Is it infinity? The answer is no, d3 equal 1. Therefore, I don't have to touch it, I don't have to modify it. Okay, so this is, this is the first issue here, that. When we come to a node, there might be multiple paths to that node from the original node. And we have to make sure that the first path that reaches that node is the path that decides the distance to it and all other paths should not touch it anymore. This is number one. Number two, which is a boundary case that we have to be careful about. And is going to be already taken care of here by this initialization is that we need to keep in mind that it is, let me say that it is very natural for, for all of us to assume that the graph is connected. But you have to be careful about boundary cases with algorithms. It might be that the user has a graph. That also has nodes 6 and 7, that are connected to each other, but they are not connected to node 0. So now, what is the distance from 0 to 6, or from 0 to 7? It's infinity? So, we have to make sure that the algorithm says that d 6. Equals infinity and d sub n equals infinity. We want this as part of the output, okay, because notice that the way the algorithm is proceeding is never going to reach six and seven because there's no path. These are not the neighbors of any of the nodes here. Okay? Fortunately, this is already taken care of, because as I said, the first thing the algorithm is going to do, is that for all nodes in the graph it's going to initialize the distance to infinity. So after the, the algorithm is done at this point, after it dealt with nodes to n5, the q is going to be empty. There is nothing more for the algorithm. To do is going to return the d values and when it returns the d values, it's going to return 0, 1, 1, 1, 2, 2, infinity, infinity, which is the correct behavior we would want from this algorithm. So with the use of the queue data structure. With knowledge that there might be multiple paths from original node to any given node and we have to keep track of that. With the knowledge that there might be nodes that are not reachable from node 0 and we have to return infinity. Now we are at the point where we can write the full description of the BFS algorithm. Which again proceeds in layers, in every layer it assigns distances to note at that layer and pushes all of them on the queue and proceeds until the queue is empty.
