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.
Digraph Search
Loading...
來自 Princeton University 的課程
Algorithms, Part II
458 個評分
從本節課中
Directed Graphs
In this lecture we study directed graphs. We begin with depth-first search and breadth-first search in digraphs and describe applications ranging from garbage collection to web crawling. Next, we introduce a depth-first search based algorithm for computing the topological order of an acyclic digraph. Finally, we implement the Kosaraju−Sharir algorithm for computing the strong components of a digraph.
與講師見面
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WayneSenior Lecturer
Computer Science
Okay. First, we're gonna look at the search algorithm for, digraphs and this is
the finding paths, what are all the vertices that we can get to from a given
vertex along a directed path. and again, this is, little more complex for a digraph
it would seem, than for a graph. so in this case, those are the, that's the set
of vertices that you can get to, from the given vertex x, s. Notice that, this set
is characterized by every edge crossing the boundary, it goes in. if there were an
edge that went out, that would give, another member of the set.. well actually,
looks more complicated to a human, but to the computer, it looks exactly, precisely
the same. in fact. the method that we looked at for undirected graphs is
actually a digraph processing algorithm. it treats, every connection between two
vertices as two directed edges, one in each direction. So, DFS, that we looked at
last time is actually a digraph algorithm. And we used precisely the same code. So to
visit a vertex V, we mark the vertex as visited, and recursively visit all
unmarked vertices W, that you can get to from V. let's look at the demo, just to, .
Reinforce that. So, here's a sample digraph with the edges over at the right.
let's look at that first search on that digraph. so, we're going to look at the
vertices that we can get to from vertex zero in this digraph. Again, we have two
vertex index to raise. one called marked, which says whether we can get there from
V, and the other called edge two, which gives us the vertex that took us there.
with that we can recover the paths from vertex zero to each vertex that can be
reached from vertex zero. So we start off by visiting vertex zero and now check the
edges that are adjacent to it with directed edges going out. so there's five
and then there's gonna be one. but five is unmarked so we have to re-cursedly visit
five. So we mark five, and we say we got there from zero. so the path from, to five
is zero to five. and so now we're gonna recursively visit all the unmarked
vertices pointed to from five . In this case it's just four. My four is
unmarked so we're gonna recursively visit four and say we got there from five. and
now recursively we have to check all the unmarked vertices pointing from four.
there's three. and two, first we do three and that's unmarked. so we gotta visit
three. and say that we got there from four. and now to visit three. We've looked
at all the vertices pointing from three. we can check five. We've already been to
five that's marked so we don't have to do anything. and then we check two. two is
unmarked so we continue with the depth first search and visit two. so now to
visit we mark two, and say we've got there from three. and now we check the vertices
that we can get two from two. In this case it's zero, which we've already been to.
And three, which we've already been to. so. now we're done with vertex two. and we
can return and continue the search from three well actually that was the last one
from three, so we're done with three as well. so now we're at four. We still have
checked the edge from four to two. so now we do that. And of course we've been to
two, so we don't have any further processing. and we're done with four. the,
, four was the only edge we get to from five. So we're going to be done with five
as well. and then, what about zero, well we have to check one. 1's not visited, so
we visit one, mark it. and we turn and then we're done with zero, and that gives,
the set of all vertices that are reachable from zero, and not only that the edge to
array. Gives the information that we need to reconstruct the path from any of those,
from zero to any of those vertices using precisely the same method that we used
before. We get the four from five, we get the five from zero, so zero, five, four is
the path to four. And we can do that for any vertex in that cell. Okay. So what
about the code? the code is exactly the same as for , undirected graphs. That's
the code for undirected graphs. that we looked at last time to get the code for
digraphs, we just changed the name, its the s ame code, otherwise. the recursive,
the constructor, builds the array of marked vertices, and also builds edge too,
just to, avoid clutter, left that one off this slide, and then it makes the call to
DFS. then the recursive DFS does the work. It marks the vertex and for every adjacent
vertex. If its not marked, it does the DFS. and then the client can ask whether
any ver-, any given vertex is reachable from s after the constructor has done its
work. that's depth-first search in directed graphs, actually, we already did
it. now here's just a couple of applications where this kind of code is
used. one is, a so called program control flow analysis. actually every program can
be viewed as a digraph. where, the vertices are basic blocks of instructions
that are just executed one after the other with no conditionals. and then edges
represent, a, jump. If there's an if statement, vertex left, two edges going
out of it, or, or a loop, which involves a conditional. So, , analyzing a program,
people write systems in analyse program, to look at their structure by studying
their diagrams, for example. one thing that happens often is there's unreachable
code. another, another thing you might want to do is determine whether you can
get to this exit or not, by doing this digraph processing. so that's actually a
widely used technique in, in developing software, software development. to try to
improve code by doing this kind of digraph-processing. And ofcourse these
digraphs can be huge. another classic use of depth for search in digraphs is garbage
collection that is used in systems like Java where data structures or digraphs. we
build objects and then we create references to other objects. and so the
data that any programs use is really set as a digraph. So there's the idea of
roots, so your program has e-. Some. live objects, that it can access through,
whatever state, it's in, but, a language like Java, there's, automatic garbage
collection, which means the programmer, when it's done with an object, maybe it
overwrites one of these pointers or something. there's gonna be some, blocks,
that, are not directly accessible by the program. and so, what's interesting is,
the set of reachable objects that, can be indirectly access. By the program starting
and following a chain of pointers. so those are the ones that can't be collected
or reclaimed by the system for reusing the memory. But all the other ones, the gray
ones that can't be reached by the program there's no reason to . Keep them live, you
may as well collect them and return them for use, re-use. So there's a so-called
marked and sweep out rhythm that actually dates back to 1960, where. We run DFS to
mark all ritual objects. and then go through and sweep through all possible
objects. And if it's object is unmarked it's garbage so add it to the list of free
memory. and that's a classic method that's still widely used. it uses an extra bit
per object'cause you have to have to have that for the mark. But still, it's
effective and useful digraph solution. So DFS with reachability that we've just
showed and path finding is similar. And there's a couple of other simple digraph
problems that we'll consider. These are so far examples. But it's also interesting
that DFS is the basis for solving digraph problems that are not so simple or
immediate to solve. And this was pointed out 40 years ago by Bob Tarjan in a
seminal paper that showed that. First search, can allow us to solve problems
that seem pretty complicated actually, in linear time, and we're gonna look at an
example of that later on. so that's depth for search. what about breadth for search.
Well in the same way that we saw for depth for search every undirected graph is
actually a digraph that has edges in both direction. So bfs is really a directed
graph algorithm and we can use exactly the same code to find shortest paths from a
source to any given vertex. So we use a que. We put the source on a que and mark
it as visited and. And as long as the queue is non-empty, we remove the least
recently added vertex and add to the que ue and mark as visited all the unmarked
vertices that you can get to from that vertex. And the same proof shows that BFS
computes shortest paths, the ones with the fewest number of edges from S to each
other vertex in the digraph in time proportional to in linear time. So you
want the GPS in your car, you BFS when you're driving around lower Manhattan. So,
let's look at the demo again just to see, the distinction between, breadth first
search, in digraphs and see how it works. So this is a, a small graphing, a smaller
digraphic and with six vertices and eight edges. we take a Q and we take a source
vertex and put on the Q to get started. then, Q is not empty, so remove zero and
we check all, all vertices that are adjacent that we get to. So. we're gonna,
in zero was zero distance, from zero, so first we will check two. and that one is
not marked, so we mark it and put it on the queue. and then we'll check one. and
that one's not marked, so we mark it and put it on the queue. then we're done with
zero. now queue's not empty so we pull the least recently added off, that's two. and
now we're going to check the vertices, you can get from two. I noticed both one and
two are distance one from zero. And now, since we're going from two, everything
that we encounter will be distance two from the source. So we find four, it's
distance two from the source, and we get there from vertex two. Unmarked, so we
fill in those data structures and put it on the queue. and then we're done with
two, so we go back to the queue, and 1's on the queue. So we pull one off and it's
distance one from zero. Remember the first showed that everything in the queue is one
of two distance, either k or k plus one. In this case, we've got one at distance
one, four at distance two. So now we're going to pull one off the queue. M- and
look at the edges you can get to, places you can get to from one. Now we check two
but that's already marked so we ignore it. and then we're done with one. Now four is
left on the Q so we pull it off and check adjacent vertices. In this case three,
it's unmarked so we put it on the Q. Then we're done with four. Then from three we
check five and that's unmarked and it's one more distance from the source so we
put it on the Q. And then finally. Oh we check two which we already visited so we
don't have to, to do anything. And then finally we pull five off the Q. check. Or
you get two from five and it's zero, which is marked, so we're done. and so that's
breadth-first search whig, which gives us this directed tree from the source. Which
gives the shortest path to all the vertices that you can get to from that
source. you can use a version of this to solve a more general problem known as the
multiple-source shortest paths problem. In this problem you're given a digraph and a
set of source vertices, and you want to find the shortest path from any vertix in
the set to each other vertix. So for example, in this case if the set is one,
seven, and ten, what's the shortest path to four? From one of those vertices. Well,
it turns out in this case to be seven, six to four. Shortest path to five is seven,
six, zero, five. Shortest path to twelve is ten to twelve. That's a more general
problem but it's actually easy to solve. How do we implement this? We just use a
different constructor. We just use BFS but initialize by, put all the source vertices
on the queue to get started. So that is every vertex is, so you put those on the
queue and they're zero from the desired source. And then any vertex you can get to
from any one of those is going to be. One and so forth, so the results still gives
away. The edge to array will still give a way to get from any vertex, the shortest
way to get from any vertex to each of the sour-, source vertices. here's an
application of depth-first search. Let's say you want to crawl the whole web, well,
all the web that you can access from some starting web page, say like Princeton's
starting webpage. Again, the digraph model, each vertex is a webpage, each edge
is a link on that webpage to some other webpage. and so all we want to do is get
to all the other vertices on the web. And, so solution is, well, we don't actually
build the digraph we just use an implicit digraph, because for every web page we can
find the links to other web pages on it and we'll just build those as we encounter
them. So we're gonna start with a source, which is the root web page. We're gonna
have a queue of the sites that we still need to explore. what we're going to do is
also have a set of discovered websites, this corresponds to our marked array but
since we don't know how many vertices there are on the web all we're going to do
is keep track of the ones that we've been to. so this is, don't use the vertex
indexed array we don't even bother with because we'll just use the vertex names
and do the look up as indicated we could do. So all we do is In the, is but for a
search the same method is if the queue's not empty. Take a website off of the cue.
And just add to the queue all the websites to which it links. but all of those
websites, you check whether they're in the set of the ones that you've seen already.
now, you might run out of space, for this set before you get to the whole web. but
anyway, conceptually, this is a way that you could go. one thing to think about is
why not use DFS for this. well One reason is you, you're gonna go far away in your
search for the web. Maybe, maybe that's what you want, but the real problem, in
point of fact is there's some web pages that would trap such a search by creating
new web pages and make links to'em the first time that you visit'em. So, they,
trap searches like that by, cuz DFS would always go to a new web page like that and
it'd keep creating new ones and you wouldn't get very far. With breadt-first
search you're taking a wide search of the pages that are close. and that's often
maybe what you want for such a search. and, just to how simple the idea is, this
is complete code for a, it's kind of a bare bones web crawler but it'll get to a
lot of websites. so let's look at, do this example because again it really indicates
the power of using appropriate abstractions to implement the algorithms
that we're interested in. so this one we're gonna use a cue. Queue of strings so
that's the websites that we have to still yet to go to. and then a set of strings is
gonna be the ones that we've already been to that's equivalent to the marked array.
we'll start with Princeton's website. add it to the queue of places we have to go
and also mark it. Discovered that ad just means mark it. so now, while the queue's
not empty. What we're going to do is read the raw HTML from the next website in the
queue. So this is code using our input library that gets that job done. And then,
this is a little fooling around with regular expressions. We'll talk about
algorithms like this later on, that essentially tries to find all URLs within
the text of that website. And for all of those URL's. And we'll. Look at workers
behind this code later on in this course. For all those URL's it's gonna check. If
it's marked that's discovered doc contains and if it's not marked it'll say it will
mark it and put it on the queue. a very s- simple program with a very powerful effect
that illustrates breadth-first search.
