But now, unlike breadth first search where we automatically went to node B next,
since that was the other layer one node.
Here, the only rule is that we have to go next to one of A's immediate neighbors.
We might go to B, but we're not going to B because it is one of the neighbor's of S,
we go because it is one of the neighbors of A.
And actually to make sure the difference is clear let's assume that we aggressively
pursue deeper when we go from A to C and now the depth first search strategy is
again to just pursue deeper, so you go to one of C's immediate neighbors, so
maybe we go to E next, so E is going to be the fourth one visited.
Now from E there's only one neighbor not counting the one that we came in on so
from E we go to D.
And D is the fifth one we see.
Now from D we have a choice, we can either go to B or we could go to C.
So let's suppose we go to C from D.
Well then we get to a node number three where we've been before.
And as usual we're going to keep track of where we've already been.
So at this point we have to back track from C back to D.
We retreat to D.
Now, there's still another outgoing edge from D to explore and
then they'll be the one to B.
And so what happens is we actually wind up wrapping all the way around this outer
cycle and we could B sixth.
And now, of course,
anywhere we try to explore we see somewhere we've already been.
So, from B we try to go to S, but we've been there so we retreat to B.
We can try to go to A but we've been there so we retreat to B.
Now we've explored all of the options out of B.
So we have to retreat from B, we have to go back to D.
Now from D we've explored both B and C so we have to retreat back to E.
We've explored the only outgoing arc D, so we have to retreat to C.
We retreat to A.
From A we actually haven't yet looked along this arc, but
that just sends us to B where we have been before.
So then we retreat back to A.
Finally we retreat back to S and S,
even at S there's still an extra edge to explore.
At S we say, we haven't tried this as B-edge yet.
But of course, when we look across we get the B where we've been before and
then we backtrack to S.
Then we've looked at every edge once, and so we stop.
So that's how depth-first search works.
You just pursue your path, you go to an immediate
neighbor as long as you can until you hit somewhere you've been before.
And then you retreat.
So you might be wondering why bother with another graph search strategy?
After all we have breadth-first search, which seemed pretty awesome, right.
It runs in linear time.
It's guaranteed to find everything you might want to find, it computes shortest
paths, it computes connected components if you embed it in a foreloop.
It kind of seems like, what else would you want?
Well, it turns out,
depth-first search is going to have its own impressive catalogue of applications,
which you can't necessarily replicate with breadth-first search.
And I'm going to focus on applications in directed graphs.
So there's going to be a simple one that we discuss in this video, and then there's
going to be a more complicated one that has a separate video devoted to it.
So in this video we're going to be discussing,
computing topological orderings of directed acyclic graphs.
That is, directed graphs that have no directed cycle.
The more complicated application is computing strongly connected components in
directed graphs.
The run time will be, essentially, the same as it was for
breadth-first search, and the best we could hope for, which is linear time.
And again, we're not assuming that there's necessarily that many edges.
There may be much fewer edges than vertices.
So linear time and these connectivity applications means O of M plus n.