0:00

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

Â 0:37

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.

Â 1:10

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.

Â 2:27

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.

Â 4:39

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?

Â 5:12

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.

Â 7:35

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.

Â