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.