Next we are going to talk about breadth-firsth search,
Which is a completely different way to process all the vertices connected to a
given vertex. It'll get the job done,
But it has totally different properties that are useful in different ways for
different applications. So, to understand a breadth-first search,
we'll start right out with a demo. So, a breadth-first search is not a
recursive algorithm. It uses a Q as a auxiliary data structure.
And it's also is quite similar 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 FIFO order then add to the queue all
unmarked vertices that are adjacent to V 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, add zero to the queue. So we just, take zero and put it on the
queue, That's where we start.
And now go into repeat until queue after remove a vertex,
Add all the marked vertex adjacent to mark'em.
So, we do qeue zero. And then, in order to process zero, we
need to check all its adjacent vertices. So in this case, it's two, one and five.
And again, the order depends on, how the, how the bag was constructed for, vertices
adjacent to zero. So, we check two, And that is, not marked.
So we have to add it to the queue. We check then we check one, That's not
marked, so we add it to the queue. Then we check five, And that's not marked,
so we add it to the queue. So, that's, we finished, processing zero,
zero is done. So now, remove the next vertex from the
queue. In this case it's two.
We're going to take two off the queue, and process this by adding to the queue all
the unmarked vertices that are adjacent. So the process two, we have to check zero,
one, three, and four. We check zero, that's already marked, so
we don't do anything. We check one, that's also already marked,
so we don't do anythin. in fact, it's on the queue.
We check three, and that one is unmarked so we mark it and add it to the queue.
And then we check four, 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 two, auxiliary data structures for this.
One is the edge two array, which is the same as before.
What edge did we use to get to this, so four.
And we got to four from two. And two, we got to two from zero.
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, we keep a more, detailed information, which
is, the length of the path, cuz it's, we do it, 'cause it's easy to do it.
Okay, so four, we checked four, and added it to the queue,
And now we're done with two. So now we have one, five, three, and four
all on 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 one, we check zero and that's
marked. Then we check two and that's marked,
So then we're done with one. Next thing off the queue is five, And we
check three and that's marked, and we check zero and that's marked, so we're
done with five. And then three, we got to check five, and
then four, 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 has
marked, So connected, check three, Check two, and
it's marked and we're done. So what this process the result of this
computation again is a three rooted at the source and we can follow back through the
three to get past from each node to the source.
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.
Alright. So now we've considered two different methods for processing all
vertices in a graph. And actually, they're quite closely
related, even though the computations are quite different.
Essentially, breadth-first search uses recursion to corresponds to putting
unvisited vertices on a stack. Breadth-first search explicitly, we put
the invert, visited vertices on the queue. And actually, breadth-first search solves,
another problem that, you know, 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 breadth-first search examines the vertices in the graph
and increasing distance from the source. So, let's take a look at that.
So breadth-first, breadth-first search computes shortest path,
That is it builds the data structure that we can answer the shortest path queries
from the source with, From S to all other vertices in the graph
and time proportial to E plus V, then [inaudible] vertices.
And so let's look at why that is the case. So the first thing is, how does, how do we
know it competes, computes shortest paths? Well, the intuition is and, you, 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 in first out order. So say we're at a state when all of these
vertices are, are on the queue. we're going to have process vertex zero, as soon
as we get this one we'll delete vertex zero from the queue, and then when we're
putting these adjacent ones on, we're adding the ones of distance two.
But we're not going to process any of those until we're done with the ones of
distance one and so forth. So it's not hard to show that always you
have either one of the two distances from, 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 cuz 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 implantation, 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 this to, But just for simplicity, let's use marked
edge two, then, is how we get to the first vertex and then the source.
And so, we have a constructor that builds those arrays same way as before and then
calls BFS. So BFS builds a queue,
That's what it's going to use. Then 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 extraction and the utility of our design pattering, pattern.
All we're doing in terms of the graph data type is being a client to go through all
the adjacent vertices. But it allows us to implement this
completely different algorithm in, in, in, really an accessible way.
So that's the implementation of breadth-first search.
Then the client for getting the pass back as be saying this as for, as for
breadth-first search. So here's an old application of
breadth-first search in, in computer networks.
That'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, the predecessor of the, internet, as
of July 1977. And things were slow and computers were,
computers were small and slow. It's important to do these things in 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. And here's another one,
So called Kevin Bacon numbers. And nowadays actually you can type Bacon
and an actor's name, And get the answer to this.
So there's if, if you're not, not familiar with it you can become familiar with it by
Kevin Bacon numbers. The idea is you have a graph, where, the
vertices are actors, and the edge, and think of an edge connecting two actors, if
they are in a movie together. and so what you wabt to find is given an actor how,
what's the shortest way to get to Kevin Bacon, connected by, so, edges were actors
and edges were movies, In connection of actors in the movie.
So Buzz Mauro and Tatiana Ramirez were in Sweet Dreams together, and these two
actors were in this movie together and so forth.
And you get a way to Kevin Bacon from any actor.
And this is another pop culture application, this is so called six
degrees, which you can get to anyone in 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 aovie And the shortest path
from Kevin Bacon to every actor, if you follow through, back through that path,
you get. To. You, you get the proof of the Kevin
Bacon number for each actor and we have implementation of that on the book side.
So that's another example. And actually there's maybe even older or
similar age example that mathematicians are fond of and that is 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 Erdos was a, a very productive
Hungarian mathematician who traveled the world co authoring papers with people all
over the world. A, a very interesting and prolific
character, who actually did quite a bit of research on properties of graphs.
And maybe even more so than Kevin Bacon. The idea is 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