0:03

Next, we're going to talk about breadth first search which

Â is a completely different way to process all the vertices to a given vertex.

Â It'll get the job done but it has a totally different properties that

Â are useful in different ways for different applications.

Â To understand breadth-first search we will start with a demo.

Â So breadth-first is not a recursive algorithm, it uses a queue

Â as a axillary data structure And it's also quite simple to explain.

Â So what we're going to do is we're going to put the source

Â vertex on a queue and then repeat the following until the queue is empty.

Â Remove the next vertex from the queue in order.

Â Then add to the queue all unmarked vertices that are adjacent to these and

Â mark them and just keep doing that until the queue is empty.

Â Let's see how that works on our example.

Â This is a smaller example, just a six vertex

Â graph with eight edges, so I add 0 to the queue.

Â So we just take 0 and put it on the queue, that's where we start.

Â And now we're going to repeat until queue is empty or remove a vertex,

Â add all unmarked vertex adjacent and mark them.

Â So we did queue 0 and then in order to process 0 we need to

Â check all of the adjacent vertices, so in this case that's 2, 1, and 5.

Â And again the order depends on how the bag was constructed for

Â vertices adjacent to zero.

Â 1:48

So we check 2 nd that is not marked,

Â so we have to add it to the queue.

Â And then we check 1, that's not marked so we add it to the queue.

Â And then we check 5, and that's not marked so we add it to the queue So

Â we finished process, 0,0 is done.

Â So now remove the next vertex from the queue.

Â In this case it's 2, we're going to take 2 off the queue and process it by

Â adding to the queue all the unmarked vertices that are adjacent.

Â So to process 2, we have to check at 0, 1,

Â 3, and 4, we check 0 that's already mark so, we going to do anything.

Â We check 1, that's also already marked so,

Â we don't do anything in fact the time to queue.

Â We check 3 and that one is unmarked so, we mark it and added to the queue and

Â then we check 4 that one's unmarked, so we mark it and add it to the queue.

Â So by the way, I didn't mention, but

Â 3:10

One is the edge to our array,

Â which is the same as before, what edge did we use to get to this?

Â So 4, and we got to 4 from 2 and 2 we have to do from 0,

Â so again that's going to be a tree that gives us a path back to the source.

Â And instead of marked, we also keep a more detailed information which is

Â the length of the path because we do it because it's easy to do it.

Â Okay, so four, we check four and add it to the queue and now we're done with two.

Â So now we have 1, 5, 3, and 4 are all in the queue and we're going to process them.

Â 4:02

checking vertices that are marked, so for 1 we check 0 and that's marked.

Â Then we check 2 and that's marked, so then we're done with 1.

Â Next thing off the queue is 5 and we checked 3 and

Â that's marked and we checked 0 and that's marked so we're done with 5 and then 3.

Â We gotta check 5 and

Â then 4 and then two and they're all marked and now we're done with three.

Â And then finally the last one, always the last one, everybody else is marked, so

Â connected.

Â Check three, check two, it's marked and we're done.

Â 4:41

So what this process [COUGH] the result of this computation,

Â again, Is a tree rooted at the source, we can follow back

Â through the tree to get paths from each node to the source.

Â And not only that, we can get the distance,

Â the number of edges on the path from each node to the source.

Â 5:05

So that's a demo of breadth first search, and

Â next we'll take a look at properties of this algorithm.

Â All right, so now we have considered two different methods for

Â processing our vertices in the graph.

Â And actually they are quite closely related eventhough the computations

Â are quite different.

Â Essentially depth-first search uses recursion so

Â it corresponds to putting unvisited vertices on a stack.

Â Breadth-first search explicitly we put the unvisited vertices on the queue.

Â And actually, breadth-first search solves another problem

Â that often we want to solve called the shortest path problem.

Â Actually, the path that you get back from breadth-first search is the path from

Â the source to the given vertex that uses the fewest number of edges.

Â And we'll look at that in just a minute and the idea is that the Breath-first

Â search examines the vertices in the graph in increasing distance from the source.

Â 6:04

So let's take a look at that, so

Â a breadth-first search computes shortest path.

Â That is it builds the data structure that we can answer sure as path

Â queries from the source with.

Â From s to all other vertices in the graph in time proportional to e + v,

Â then there are plus some more vertices and so let's look at why that's the case.

Â So first thing is, how do we know that it computes, has shortest pass?

Â Well the intuition is, and you can fill in the details,

Â 6:42

the queue always contains some vertices of

Â distance k from the source, followed by some vertices of distance k plus one.

Â So they're on a queue, we're processing them in first and first out order.

Â So say we're at a state when all of these vertices are on the queue.

Â 7:07

We're going to have processed vertex 0 as soon as we get this one

Â we'll delete vertex 0 from the queue and then we're putting these adjacent ones on.

Â We're adding the length of distance too but we're not going to

Â process any of those until we're done with the ones at distance 1 and so forth.

Â So it's not hard to show that always,

Â you have either one of the two distances from the source on the queue.

Â And that means the first time we get to a vertex,

Â that's the shortest path to that vertex.

Â 7:38

And, again, the running time, we only visit vertices once because we mark them.

Â So, it's time proportional to the number of vertices

Â plus the number of edges in the graph.

Â So, that's breadth-first search properties and

Â then here's the implementation, which is simply code for

Â 8:30

So BFS builds a queue, that's what it's going to use and

Â queues the source and marks the source.

Â And then this is just in code what we said in words before, while the queue is

Â not empty, we pull off the next vertex from the queue, call it v.

Â For everybody adjacent to v, we go ahead and check.

Â If it's marked, we ignore it and move to the next If it's not marked,

Â then we put it on the queue, mark it, and remember the edge.

Â And again, this is an example of the power of abstraction and

Â utility of our design pattern.

Â 9:17

All we're doing in terms of

Â data type as being a client to go through all the adjacent vertices.

Â But it allows us to implement this completely different algorithm

Â in really an accessible way.

Â So that's the implementation of for search and then the client for

Â getting the paths back.

Â It's going to be the same as for depths for search, so

Â here's an old example of breadth-first search.

Â And in computer networks it's very important when you're communicating

Â from one place to another you want to get there in the fewest number of hops.

Â This is the ARPANET the predecessor to the internet as of

Â July 1977 when things were slow and computers were small and

Â slow, it's important to do these things in a small number of hops.

Â And with breadth-first search, you could take this graph and

Â figure out the shortest way to get from one place to another.

Â That's a typical application of breadth-first search.

Â 10:26

Here's another one, so-called Kevin Bacon number, and nowadays actually

Â you can type Bacon and an actor's name and get the answer to this.

Â So there's,

Â if you're not familiar with it, you can become familiar with it by Kevin Bacon,

Â or the idea is you have a graph where the vertices are actors.

Â And the edge,

Â you think of an edge connecting two actors, if they were in a movie together.

Â And so, what you want to find is given an actor,

Â [COUGH] what's the shortest way to get to

Â Kevin Bacon connected by, so, we have ed is for

Â actors and edge is for movies in a connection of actors in the movie.

Â So Buzz Mauro and Tina Ramirez were in Sweet Dreams together and

Â these two actors were in this movie together and so forth.

Â And you get away to Kevin Bacon from any actor and

Â this is another pop culture application.

Â This is the so-called six degrees, which you can get to anyone with six steps

Â in this way, so that's all implementation of breadth first search.

Â On the Kevin Bacon graph, where we include one vertex for

Â each performer, one vertex for each movie.

Â Connect the movie to all performers that appear in the movie, and the shortest

Â path from Kevin Bacon to every actor if you follow back through that path.

Â You get the proof of the got a Kevin Bacon number for

Â each actor and we have implementation of that on the book site.

Â 12:19

So that's another example, and actually there's a maybe even older service,

Â at least similar age example that mathematicians are fond of.

Â And that's called the so-called Erdos number.

Â So, in this one it's mathematicians, the nodes are mathematicians and

Â there's an edge if the two mathematicians have co-authored a paper and

Â Paul was a very productive Hungarian mathematician.

Â Who travelled the world co-authoring papers with people all over the world.

Â A very interesting and prolific character who actually did

Â quite a bit of research on properties of and maybe even more so than Kevin Bacon.

Â The idea that he was so prolific that pretty much every

Â mathematician has a pretty low Erdos number.

Â So that's our second example of a graph processing algorithm,

Â breadth-first search.

Â