Tip:
Highlight text to annotate it
X
Let's explore our second strategy for graph search, namely depth-first search.
And again, like with breadth-first search, I'll open by just reminding you what the
depth-first search is good for. And we'll trace through it in a particular example
and then we'll tell you what the actual code is. So if breath-first search is the
cautious and tentative exploration strategy, then depth-first search or DFS
for short is its more aggressive cousin. So the plan is to explore aggressively and
only backtrack when necessary. And this is very much the strategy one often
uses when trying to solve a maze. >>To explain what I mean, let me show you how
this would work in the same running example we used when we discussed breath-first
search. So here if we invoke depth-first search from the node number S.
Here's what's gonna happen, so obviously we start at S and obviously there's two
places where we can go next. We can go to A or, or to B, and depth-first search is
underdetermined like breath-first search, we can pick either one. So like with the
breath-first search example, let's go to A first. So A will be the second one that
we explore. 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. So we might go to B but we're
not going to B because it's one of the neighbors of S, we go because it's one of
the neighbors of A, and actually to make sure the difference is clear, let's assume
that we aggressively pursue deeper and we go from A to C. And now the depth-first
search strategy is, again, just to 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 can 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, okay? And as usual we're
going to keep track of where we've already been. So at this point we have to
backtrack from C back to D, we retreat to D. Now there's still another outgoing edge
from D to explore, namely the one to B. And so what happens is, we actually wind
up wrapping all the way around this outer cycle. And we hit 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 try, 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. E we've explored the
only outgoing mark D, so we have to retreat to C. C we retreat to A. From A,
we actually haven't yet looked along this arc. But that just sends to B where we've
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, oh we haven't tried
this S-B edge yet but, of course, when we look across, we get to B where we've been
before and then we backtrack to S. Then we've looked at every edge once and so we
stop. 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 you know why bother
with another graph search strategy. After all we have breadth-first search which seems
pretty awesome right? It runs in linear time. It's guaranteed to find everything
you might wanna find. It computes shortest paths. It computes connected components if
you imbed it in a for loop. Kinda seems like what else would you want? Well, it turns
out depth-first search is gonna have its own impressive catalog of applications which
you can't necessarily replicate with breadth-first search. And I'm gonna focus on
applications in directed graphs. So there's gonna be a simple one that we
discuss in this video. And then there's gonna be a more complicated one that has a
separate video devoted to it. So in this video, we're gonna 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 in these connectivity
applications means O(M+N). >>So let's now talk about the actual code of
depth-first search. There's a couple ways to do it. One way to do it is to just make
some minor modifications to the code for breadth-first search. The primary
difference being instead of using a queue at its first-in-first-out behavior, you
swap in a stack where it's last-in-first-out behavior. Again, if you don't know
what a stack is you should read about that in the programming textbook or on the web.
It's something that supports constant-time insertions to the front and constant
time deletions from the front, unlike a queue which is meant to support constant-time
deletions to the back. Okay, so stack. It operates just like those
cafeteria trays that you know where you put in a tray, and the last one that got
pushed in, when you take the first one out, that's the last one that got put in.
So these are called push and pop. In a stack context, both are constant time. So
if you swap out the queue, you swap in the stack, make a couple other minor
modifications, breadth-first search turns into depth-first search. For the sake of
both variety and elegance, I'm, instead, gonna show you a recursive version. So
depth-first search is very naturally phrased as a recursive algorithm, and
that's why we'll discuss here. So depth-first search, of course, takes as input
a graph G. And, again, it could be undirected or directed, it doesn't matter.
Just, with the directed graph, be sure that you only follow arcs in the
appropriate direction, which should be automatically handled in the adjacency
lists of your graph data structure anyways. So, as always, we keep
a boolean local to each vertex of the graph, remembering whether we've,
start, we've been there before or not. And of course as soon as we start
exploring for S, we'd better make a note that, now we have been there. We better
plant a flag, as it were. And remember, that depth-first search is an aggressive search.
So we immediately try to recursively search from any of S's neighbors that we
haven't already been to. And if we find such a vertex, if we find, somewhere we've
never been, we recursively call depth-first search, from that node. The basic
guarantees of depth-first search are exactly the same as they were for
breadth-first search. We find everything we could possibly hope to find and we do it
in linear time. And once again the reason is this is simply a special case of the
generic search of procedure that we started this sequence of videos about.
So it just corresponds to a particular way of choosing amongst
multiple crossing edges between the region of explored nodes and the region of
unexplored nodes, essentially always being biased toward the most recently discovered
explored nodes. And just like breadth-first search, the running time is going to
be proportional to the size of the component that you're discovering. And the
basic reason is that each node is looked at only once, right? This boolean makes
sure that we don't ever explore a node more than once and then for each edge, we
look at it at most twice, one from each end point. And given that these exact same two
claims hold for depth-first search as for breadth-first search, that means if we
wanted to compute connected components in an undirected graph, we could equally well
use an outer for loop with depth-first search as our work horse in the inner
loop. It wouldn't matter. Either of those for undirected graphs, depth-first search,
breadth-first search is gonna find all the connected components in O(M+N) time,
in linear time. So, instead, I wanna look at an application particular to depth-first
search, and this is about finding a topological ordering of a directed acyclic graph.