0:00

Okay. Now that we have,

Â we have gotten to a point where we wrote the BFS algorithm formally,

Â we can describe the entire algorithm.

Â Let us illustrate how this algorithm would work,

Â how we're going to make use of the queues, and how it will compute the distances.

Â This is the algorithm, this is the pseudo code of the algorithm and

Â this is an example of a graph that we have been, we have been working with.

Â Remember, this is an algorithm that takes as input a graph, like this one,

Â a source node, in this case, I'm going to assume it is zero, and

Â it's going to compute the distance, dj, to every node, j, from node zero.

Â Okay?

Â So in this case, this is our graph and the initial node, i, is 0.

Â Okay?

Â So [COUGH] how is this algorithm going to work?

Â I will, we will keep track of djs.

Â The first thing that the algorithm does, is that it initializes Q to an empty Q.

Â So we start with, I'm going to have Q here.

Â 1:00

And, this is the first thing in the first line.

Â Then, it says, for every node j, initialize the distance to infinity.

Â So, we are going to have now, d 0, equal infinity.

Â D1 equals infinity.

Â And d3 equals infinity, d4 equals infinity,

Â d2 equals infinity and d5 equals infinity.

Â This is, now we are done with lines 1, 2, and 3.

Â Then the fourth thing it says d i is 0.

Â What, let's set the d i to 0, i is the specific node that's part of the input.

Â So we are going to go [COUGH] things that, that, i is zero,

Â we are going to go to node zero and now we'll reset its distance to zero.

Â From infinity to zero.

Â Okay? So now, this distance is zero, here, okay?

Â And the next thing we'll do is that we will push that node i onto the queue.

Â So now the queue is going to have node i, which is zero.

Â I is zero, therefore the queue is going to have zero.

Â The, the convention I'm going to use is that the head of the Q is on the left,

Â the tail of the Q is on the right.

Â So every time I add something to the Q, I'm going to add it on the right.

Â Every time I take something out of the Q I'm going to take it from the left.

Â So now after line five, we have distance to node: zero, zero.

Â The distance to every other node is infinity.

Â The Q has only one element on it which is node zero.

Â The initial node.

Â Then we go into this wide loop, and

Â this loop says as long as the Q is not empty, do the following work.

Â We look at the Q, is it empty?

Â The answer is no.

Â So we go into this loop and start doing work here.

Â What is says first is j is dQ of Q.

Â So take an element from the Q.

Â Remember, this is not a random element, this is not any operation we can,

Â we can have in mind.

Â This says that remove the element that's at the head of the Q.

Â So in our, in our drawing there,

Â remove the leftmost element in that list that I'm showing.

Â J is going to take that node so

Â now at this point, j is the element at the, at the Q.

Â 3:12

J is going to be zero, okay?

Â So it's going to, when we do dQ, then that element not only do we see what's on the,

Â in the head of the Q, but we also remove it.

Â So dQ removes the element from the Q and returned it to us.

Â So now after this step, I have the Q is empty, okay?

Â So now, j is, is zero, the Q is empty.

Â Then we say for each neighbor, h of j.

Â For each neighbor, h of j, what are the possible values of h?

Â J is 0.

Â I go now to the graph.

Â I say, okay, what are the neighbors of this?

Â For each neighbor, it's going to go through them in some sort of order.

Â Okay?

Â There is no specific order, doesn't have to go 1, 3, 4.

Â It can go 3, 1, 4, 3, 4, 1, or 4, 1, 3, and so on.

Â We can, we can use, for

Â example, let's just, to make sure that nobody misunderstands things.

Â Let's assume that it's actually going to try the neighbors in the order of 3,

Â then 1, then 4, okay?

Â 4:13

So first, it's going to go to h, the first neighbor is going to consider,

Â is going to be node 3, okay?

Â So, it says for each neighbor, the first one is node 3.

Â If dh equal infinity do.

Â Is d of 3 infinity?

Â The answer is yes.

Â So this condition holds.

Â So we come to this point here.

Â When we come here, we say, d h is d h, d h is d j plus 1, sorry.

Â This is d j plus 1.

Â Dh is dj plus 1.

Â D j, remember j is 0.

Â It's d0 plus 1.

Â D 0 is 0.

Â D0 plus 1 is going to be 1.

Â So now, d3 gets updated, and its distance is 1.

Â Okay?

Â 4:59

Once we update the distance to node 3, we push left node into the Q.

Â So now the Q which was empty, we put, put the node H.

Â H is 3, so 3 goes into the Q.

Â Okay?

Â We are done with node 3.

Â We come back to this loop for the next neighbor of, of node j, which is node 0.

Â We say that the next one we are going to consider, for example, is node 1.

Â So we come to node 1.

Â Now we look at h equal 1.

Â We ask, is d of 1 infinity?

Â The answer is yes.

Â What we do, is we update the distance of 1 to be d of 0 plus 1, which becomes 1 now.

Â 6:02

H is 4.

Â We ask, is d of 4 infinity?

Â The answer is, yes.

Â We come here, we update d of fourth to be d j plus 1,

Â d0 plus 1 which is 0 plus 1, which is 1.

Â So this is updated now.

Â Once this update, we add the node 4 on to the queue.

Â Again it is added to the tail.

Â Okay?

Â Now, we come back to this loop.

Â To say for each neighbor are there any more neighbors of node 0?

Â The answer is no, so we are done with this.

Â Okay? We are done with this for node zero.

Â We exit from here.

Â We come back to this loop that says while Q is not empty do.

Â Is the queue empty?

Â The answer is no, so we come back to this, inside this loop.

Â Then since the queue is not empty,

Â the first thing we do is that j is the element at the head of the queue.

Â Now, when we look at the queue,

Â what is the element that's at the head of the queue?

Â It is 3.

Â So j, now, is node 3.

Â Since we dequeued it, it is gone from the queue.

Â 7:11

We have node 3 here, we now ask for every neighbor, H of, of J.

Â J is 3.

Â Now let's look at every neighbor of node 3.

Â So what are the neighbors of node 3?

Â It has two neighbors, 0 and 1.

Â So the first one is h, is 0.

Â We ask is d of 0 infinity?

Â 7:47

Then we ask, what about other neighbors, there are no more neighbors, we are done.

Â Okay?

Â So actually, when we came to node 3, and

Â we looked at all of our, of its neighbors, since none of them had distance infinity,

Â actually it was nothing done by the algorithm here.

Â Okay?

Â So now we come back, and say, now, is the queue empty?

Â The answer is no.

Â We say remove an element from the queue and put in j.

Â This now becomes j now is 1, and the queue is in this state.

Â Now we go to node 1, we say for every neighbor h of node 1 do.

Â What are the neighbors of node 1?

Â They are 0, 3 and 2, okay?

Â So the first h is going to be 0.

Â We are going to come here as d 0 infinity, the answer is no, we don't do anything.

Â We look at another neighbor.

Â Another neighbor of node 1 is node 3.

Â 8:51

Is d of 2 infinity?

Â The answer is yes.

Â So now we say d of h, h is 2, d of 2, is d of j plus 1,

Â j is 1, so this d of 2 is going to be d of 1 plus 1.

Â D of 1 is 1, plus 1 is going to be 2.

Â So now this gets updated.

Â We put, we put this node h on the queue.

Â So node 2 now goes onto the queue, and it goes again on the right.

Â 9:22

Okay?

Â Now we are done with node, with node 2, with node 1.

Â There are no more neighbors of it.

Â We come back to the queue.

Â We come back to the queue, we said okay, now remove an element from the queue and

Â put it in j.

Â The next one is going to be 4.

Â So j now is 4.

Â And now, what happens here?

Â For 4, we say okay, let's look at all the neighbors of 4.

Â The first neighbor is going to be zero.

Â H is 0.

Â We say is d of, of 0 infinity?

Â The answer is no, so nothing happens.

Â We look at the next neighbor of 4.

Â Next neighbor is 2.

Â Is d of 2 infinity?

Â The answer is no, we don't do anything.

Â We look another neighbor of 4, which is 5.

Â So now h is 5.

Â 10:12

Is D of 5 infinity?

Â The answer is yes.

Â Since d of 5 is infinity, now if we update its distance,

Â d of 5 is going to take d of 4 plus 1, because j is 4.

Â D of 4 is 1, plus 1 is going to be 2.

Â We update this to 2.

Â And we put h under the queue, which is node 5.

Â Now, node 5 goes into the queue.

Â 10:35

And again, because we, I forgot, since j is 4, we had to de-queue it first.

Â So it's not there.

Â And this is now the state of the Q.

Â [COUGH] We come back to this, to this line, is queue empty?

Â The answer is no, we d q the, here we get an element from it,

Â it's going to be two, once we get 2 j is 2 now.

Â [SOUND] j is 2.

Â We look at all the neighbors of j, [COUGH], it has two neighbors, h,

Â it has neighbor 1 and neighbor 4, but d for

Â both of these nodes is not infinity, so we don't do anything.

Â So once we look at 2,

Â its neighbors, the distances have been computed, we don't do anything.

Â We remove 2, we, we are done with 2.

Â We come to the Q, is it empty?

Â The answer is no.

Â We take, we take the element on the Qj, in this case it's going to be 5.

Â 11:34

We come to 5, we ask about all the neighbors of 5.

Â It has one neighbor 4, is d of 4 infinity?

Â The answer is no.

Â D of 4 is 1.

Â We don't do anything.

Â We come back to the, to this line, while Q is not empty.

Â We look a the Q, it is already empty.

Â So we cannot, we don't do anything here.

Â We come back to this line, we say return d.

Â D is, d 0 is 0.

Â D 1 is 1.

Â D 3 is 1.

Â D 4 is 1.

Â D 5 is 2.

Â D 5 is 2.

Â So we are done.

Â This is how the algorithm would run.

Â Now notice that if there was again node 6 here, that is not connected to anything,

Â this node would not have been added to the queue at any point,

Â in the initialization step, it would have gotten d, d 6 equal infinity, and

Â by the time we have finished the algorithm, it wouldn't have been touched.

Â Therefore when we return d, it would have returned d6 infinity.

Â Okay?

Â And this is how this algorithm works.

Â