Now one of the things to remember is in a computer representation normally we're

just looking at the vertices and the set of associated edges.

We don't see anything other than that. Though, it's sometimes frustrating

watching me you know that it turned the wrong way and it's gonna get trapped here.

But, the computer doesn't really know that, so it has to back up along here now

and it continues to back up to find another option untill it gets free again.

And finds a some place to go. Sometimes its very frustrating.

Its seems to be quite close to the goal like appear and it turns a wrong way.

So we an see its gonna take a long way but no way the program could really know that.

Again, all the programs we're working with is vertex instead of edges associated with

that vertex and there it finally get to the goal.

Here's a bigger one going faster. The king thing is not so much, its getting

lost and the key thing is not going anywhere twice.

And that's the whole thing. We have to have the string to know to go

back where we came from. And we have to be able to mark where we

have been. And with those two things we are,

algorithm is, able to avoid going the same place twice.

If you weren't marking, if you tried to do this randomly or some other way it might

take you a while to get to the goal. So it doesn't seem like much of

accomplishment maybe for a maze but actually to be able to get there with

going, without going any place thrice, twice is sort of a, profound idea and

leads to an efficient algorithm. Okay.

So, our idea is, given in this, medicode, to do, depth research, that is, to, visit,

all the places you can get to from a vertex, V.

What we're gonna do is this simple re, recursive algorithm.

Mark the vertex as visited and then recursively visit all unmarked vertices, W

that are adjacent to V. That's a very simple description, and it

leads to very simple codes. It's so simple actually, it really belies

the profound idea underneath this algorithm.

So, again, There's lots of applications. And, for example, this is one way to find

whether there exists a path between two vertices.

Or to find all the vertices connected to a given source vertex.

And we'll consider some less abstract applications, once we've looked at the

code. So, so how to implement.

Well here's what we're gonna do for our design pattern for graph processing.

It's our first example. So what we did, when we defined an API for

graph was to decouple the graph data type from graph processing.

The idea is we're gonna create a graph object using that API which we know allows

us to represent a big graph within the computer.

And gives us the basic operations that we're gonna need for graph processing.

And then we use that API within a graph processing routine.

And the basic idea is that, that graph, graph processing routine will go through

the graph and collect some information. And then a client of that routine will

query the it's API to get information about the graph.

So in the case of, depth first search. Here's a potential possible API.

So the idea is that what this, what we're gonna implement is a program that can find

paths in a graph from a given source. So we give a graph and a vertex.

And that the constructor is gonna do what it needs in order to be able to answer,

these two queries. First one is, give a vertex,

Client will give a vertex. Is there a path in the graph, from the

source to that vertex? You wanna be able to, answer that

efficiently. And then,

The other thing is to just give the path. What's the path from, has to be giving all

the vertices on the path, in time proportional to its length.

So here's a client of, this, API. So, it's gonna take a source, a source

vertex S. And it's gonna build a pathfinder, or a

path object. And that object is gonna do the processing

it needs to be able to efficiently implement hasPathTo. And then what this

does is for every vertex in the graph. If there's a path from s to that vertex.

It'll print it out. So it prints out all the vertices

connected to x. And that's just one client, of this, data

type. You could, print out the pass or whatever

else you might. So that's our design pattern that we're

gonna use over and over again, for, A graph processing routine.

And it's important to understand why we use a design pattern like this.

We're decoupling the graph representation from the processing of it.

As I mentioned, there's hundreds of routines for, or algorithms that have been

developed for processing graphs. An alternative might be to put all of

those algorithms in one big data type. That's a so called fat interface.

And that would be a, a bad plan, cuz these things maybe are not so well related to

each other. And actually all of them really are just

iterating through the graph, and doing different types of processing.

With this way we're able to separate out. The, and I articulate what the graph

processing clients are doing. And then the real applications can be

clients, of these graph processing routines.

And everybody's taken advantage of an efficient representation, that we already

took care of. Okay.

So now let's look at a demo of how depth-first search is gonna work and then

we'll take a look at the implementation. Okay.

So here's a demo of depth-first search in operation on our sample graph.

Again, to visit a vertex we're gonna mark it, and then recursively visit all

unmarked verti-, vertices that are adjacent.

So this is a sample graph. And so the first thing we do is realize

that we're gonna need a vertex index array to keep track of which vertices are more.

So that will just be an array of bullions and we'll initialize that with all false.

We're also gonna keep another data structure.

A, a vertex indexed array of ints. That for every vertex gives us the vertex

that took us there. So, let's get started and you'll see how

it works. So this is depth-first search staring at

vertex zero. So now to visit vertex zero, we wanna mark

it so that's, our mark zero is true. That's the starting points we know

anything with Edge two. And now what we're gonna do is.

We're going to need to check all the vertices that are adjacent to zero.

So that's six, two, one, and five. The order in which they're checked depends

on the representations in the bag. We don'tr really, necessarily care about

that. Most of the algorithms are going to check

them all. And it doesn't matter that much about the

order. Although, in some cases it's wise to be

mindful. And maybe use a bag that takes them out in

random order. Okay this is zero.

Now we have to check, six, two, one, and five so, lets go ahead and do that.

So in this case six, six is the first thing to get checked.

And so now, we mark, six is visited so now we are going to recursively do a search

starting from six. The other difference when we visit six

from zero. We're going to put a zero in this edge to

entry to say that when we first got the six the way we got there, was from zero.

And that's going to be the data structure that'll help us, implement the client

query and give us the path back to zero from any path.

From any vertex. So okay what do we have to do to visit

six. Well six has two adjacent vertices zero

and four. So we're gonna have to check them.

So first we check zero and that's already marked.

So we don't really have to do anything. We're only suppose to recursively visit

unmarked vertices. And then we check four.

And four is unmarked, so we're going to have to recursively visit is.

The next thing we do is visit four. Mark four as having been visited.

Where the true and the marked array, Fourth entry is a marked array.

And we fill an edge two saying we got to four from six.

And so now to visit four, we have to recursively check five, six and three, and

again, that order is where they happen to be in our bag.

So first we check five. Five is not marked so we're going to visit

five. We're gonna mark it.

Say we got there from four, and then go ahead and visit three, four and zero, in

that order. From first we visit three.

That one also is not yet marked, so we're gonna recursively visit it.

So it's marked three. Say we got there from five and then go

ahead and to visit three recursively, we have to check five and four.

Check five. Well we just came here it's mark, so we

don't have to do anything. Check four, that's also, been marked so we

don't have to do anything. So now finally, this is the first time and

that requires a call that we're ready to return, we're done with that first search

from three. So now we're done with three.

And we can unwinding the recursion, we can now continue our search from five.

And the next thing we have to do from five, we had already checked three, so now

we're gonna check four. And we've already visited four, so we

don't have to do anything. That's already marked.

And we checked zero, and that one's already marked.

So now we're done with five, and we can back one more level up in the recursion.

So now, for four, we have to go through, and look at six and three.

Six is mar, marked, so we don't have to do anything.

Three is marked, so we don't have to do anything, and so we're gonna be done with

four. So that after finishing four we're done

with six. And so now we're in the recursion back at

zero. And we've already checked six.

So now we gotta check two next. We checked two, and so we rehearse and go

there. Mark two, and then say we got there from

zero, and now to visit two, all we check is zero and that's a marks, so we don't

have to do anything, and we're done with two.

Then check one, visit one, that's the last vertex we're visiting.

Check zero, it's already marked so we don't do anything.

We return. Now, we're at the last, step is to, from

zero, five is on it's list, we have to check if we've been there.

We can see that it's marked and we have been there so we're one with zero.

So that's a depth-first search from vertex zero, and we have visited all the vertices

that are reachable from zero. Number one and number two for each one of

those vertexes we kept track of how we got there from zero.

So if we now want to know for any one of those vertices how to get back to zero we

have the information that we need. For example say we want to find the path

from five back to zero. We know we got the five from four, we know

we got the four from six, we know we got the six from zero so we can go back

through using that edge to array to find. The path, so the depth for search

calculation built in data structures, and now clients, whose data structures built

in a constructor serve as the basis for, being able to.

Officially answer client queries. That's a depth-first search demo.

So, this is just a summary of the thing I talked about, during that demo.

Our goal is to find all the vertices connected to different vertex at.

And also a path, in order to be able to answer client query.

On the algorithm we're going to use is based on like maze exploration where we

use excursion, mark each vertex, keep track of the edge we took to visit it and

return when there's no unvisited options. We're using, two data structures, to

implement this. Both vertex indexed arrays.

One named Mark that will tell us which vertices we've been to.

And another one, edge two that maintains that tree of paths.

Where edge 2W = V means that VW was taken, the first time that we went to W.

So now, let's look at the code, that, given all of this background.

The code for implementing depth first search is remarkably compact.

So here's our private instance variables. The marked and edgedTo vertex and mix

arrays, and the source s. And the constructor just goes through and,

creates, the arrays and initializes them. And we won't repeat that code.

And so here's the, the last thing the constructor does after it creates the

arrays, is does a DFS on the graph, from the given source.

And it's a remarkably, compact implementation to do depth-first search,

from a vertex V. What we do is mark V, let's say mark it

true. Then for everybody adjacent to V.

We check if it's marked. If it's not marked, then we do a recursive

call. And we set edge to w equals v.

Again remarkably compact code that gets the job done.