All right, so let's take a look at the algorithm in a bit more detail.
We're going to dive into step 1.
So, step 1 says perform a depth first search on the whole graph.
Now this is a very similar depth first search to what we did in our previous
courses, except for our goal here is not to find a path from a start to a goal.
It's actually just to visit all the nodes in the graph and
keep track of the order in which we finish exploring from each particular node.
So we're dividing this approach up into two different methods.
So we have our DFS method at the top, and what that's doing is it's just iterating
over all the nodes in the graph and visiting each one with this DFS-VISIT,
which is this algorithm I'll talk about in a second, if it hasn't yet been visited.
And the reason we need this is because if the nodes aren't reachable from that
first node where you start,
your DFS-VISIT won't actually reach all the nodes in the graph so you might need
to iterate over the remaining nodes to visit them in this DFS algorithm.
And you'll see how that works in just a second.
Ang then the DFS-VISIT is really the core.
That's where most of the work is doing with the actual depth first search.
It's using recursion, don't be too alarmed by that.
I'll talk a little bit about how recursion works
as we get into this algorithm in a little more detail.
But basically, all you need to know is that when you see that call to DFS-VISIT
from the middle of DFS-VISIT,
it just goes back to the top of the function as if it were any other function.
All right,
let me just dive in and show you how it works on this particular example.
So importantly, this is going to maintain a couple of data structures.
So DFS is going to have a stack of vertices that's going to determine
the order in which those vertices are explored, visited in that main DFS loop.
And then it's going to have a finished stack.
So as we finish each vertex,
as we completely finish exploring from that vertex,
we're going to put it onto this stack called the finished stack, and you'll see
a line there down at the end of the DFS-VISIT that adds nodes to the stack.
All right, so let's get started.
The first thing we do is, while this vertices stack is not empty,
we're going to take the first node off of that stack, and
in this case the first node is 18.
So, we took it off the stack, this is the node that we're going to
now do DFS-VISIT on because it hasn't yet been visited.
So, call DFS-VISIT, jump down into DFS-VISIT.
We're going to visit it.
So, ordinarily, we might add it to some set a visited notes, but
I'll just turn it grey for the purpose of this example.
So 18 is now grey, it's been visited.
But now we're going to do our dept first search from node 18.
So we're going to find its neighbors, there they are,
and for each of those neighbors, if it already hasn't been visited,
it's going to call DFS-VISIT recursively on that neighbor.
So let's take the neighbor, for example, 23.
And so 23 is going to go back into DFS-VISIT as now the new argument v.