This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.
Breadth-First Search
Loading...
Do curso por Princeton University
Algorithms, Part II
424 ratings
Na lição
Undirected Graphs
We define an undirected graph API and consider the adjacency-matrix and adjacency-lists representations. We introduce two classic algorithms for searching a graph—depth-first search and breadth-first search. We also consider the problem of computing connected components and conclude with related problems and applications.
Conheça os instrutores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WayneSenior Lecturer
Computer Science
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.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
