Breadth-First Search

Loading...

Из курса от партнера Princeton University

Algorithms, Part II

770 оценки

Princeton University

Algorithms, Part II

770 оценки

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. All the features of this course are available for free. It does not offer a certificate upon completion.

Из урока

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.

Introduction to Graphs9:32

Depth-First Search26:22

Breadth-First Search13:34

Connected Components18:56

Graph Challenges14:29

Познакомьтесь с преподавателями

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science
Kevin Wayne
Phillip Y. Goldman '86 Senior 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.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play