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. 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 we're also keeping track of 2 auxiliary data structures for this. 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. And since we've marked everything, all we're going to be doing now is 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. 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. 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. 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, 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. 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. 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 the basic method that we outlined in pseudocode. So our private instance variables are marked, or in the demo we used disk to, but just for simplicity let's use marked. Edge two then is how we get to the frist vortex and then the source. And so I have a constructor that builds those arrays the same way as before and then calls BFS. 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. 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. 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. 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.
