0:00

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

Â 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 breadth-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 back track 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 breadth-first search.

Â So here if we invoke depth-first search from the node number S,

Â here's what's going to happen.

Â So obviously we start at S and obviously there's two places where we can go next.

Â We can go to A or to B.

Â And depth-first search is under determine like breadth-first search we can

Â pick either one.

Â Select with a breadth-first search example let's go to A first.

Â So A will be the second one that we explore.

Â 1:03

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.

Â 4:17

So let's not talk about the actual code of depth for search.

Â There's a couple of ways to do it.

Â One way to do it is to just make some minor modifications to the code for

Â breadth for a search.

Â The primary difference being instead of using a queue in its

Â first in first out behavior, you swap in a stack with its last in first out behavior.

Â Again, if you don't know what a stack is you should read about that in the program

Â 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 that 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 going to show you a recursive version.

Â So depth-first search is very naturally phrased as a recursive algorithm,

Â and that's what 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 a 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 been there before or not.

Â And of course, as soon as we start exploring from S we better make a note

Â that now we have been there.

Â We better plant a flag, as it were.

Â And remember, 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 now, if we find such a vertex, if we find somewhere we've never been,

Â we recursively call depth-first search from that node.

Â 6:06

The basic guarantees of depth-first search are exactly the same as they were for

Â breath-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

Â stretch 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

Â between the region of unexplored nodes.

Â Essentially always being biased toward the most recently discovered explored nodes.

Â And just like, breadth for 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, once from each endpoint.

Â 6:53

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 workhorse in the inner loop.

Â It wouldn't matter.

Â Either of those for undirected graphs, depth-first search, breadth-first search,

Â is going to find all the connected components in O of n plus m time,

Â in linear time.

Â So instead, I want to focus on an application in particular to depth-first

Â search, and

Â this is about finding a topological ordering of a directed acyclic graph.

Â