Depth-First Search (DFS) & Topological Sort | MIT 6.006 Algorithms (Lecture 14) Tutorial Guide Algorithm Graph Theory Computer Science Educational Video DFS Tutorial Topological Sort MIT Algorithms 6.006 DFS Algorithm Topological Sorting Graph Cycles MIT OCW Introduction to Algorithms Depth First Search Topological Sort MIT Lecture Graph Algorithms DFS Cycle Detection Curriculum Guide Learning Resource Video Lecture Tutorial Guide Algorithm Explanation Depth-First Search Graph Algorithm Topologi

[00:00:00]The following content is provided under a Creative Commons license.

[00:00:04]Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free.

[00:00:10]To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu PROFESSOR: All right, let's get started.

[00:00:24]We return today to graph search.

[00:00:27]Last time we saw breadth-first search, today we're going to do depth-first search.

[00:00:31]It's a simple algorithm, but you can do lots of cool things with it.

[00:00:34]And that's what I'll spend most of today on, in particular, telling whether your graph has a cycle, and something called topological sort.

[00:00:42]As usual, basically in all graph algorithms in this class, the input, the way the graph is specified is as an adjacency list, or I guess adjacency list plural.

[00:00:52]So you have a bunch of lists, each one says for each vertex, what are the vertices I'm connected to?

[00:00:58]What are the vertices I can get to in one step via an edge?

[00:01:02]So that's our input and our goal, in general, with graph search is to explore the graph.

[00:01:08]In particular, the kind of exploration we're going to be doing today is to visit all the vertices, in some order, and visit each vertex only once.

[00:01:17]So the way we did breadth-first search, breadth-first search was really good.

[00:01:20]It explored things layer by layer, and that was nice because it gave us shortest paths, it gave us the fastest way to get to everywhere, from a particular source, vertex s.

[00:01:31]But if you can't get from s to your vertex, than the shortest way to get there is infinity, there's no way to get there.

[00:01:39]And BFS is good for detecting that, it can tell you which vertices are unreachable from s.

[00:01:46]DFS can do that as well, but it's often used to explore the whole graph, not just the part reachable from s, and so we're going to see how to do that today.

[00:01:55]This trick could be used for be BFS or for DFS, but we're going to do it here for DFS, because that's more common, let's say.

[00:02:07]So DFS.

[00:02:21]So depth-first search is kind of like how you solve a maze.

[00:02:24]Like, the other weekend I was at the big corn maze in central Massachusetts, and it's easy to get lost in there, in particular, because I didn't bring any bread crumbs.

[00:02:36]The proper way to solve a maze, if you're in there and all you can do is see which way to go next and then walk a little bit to the next junction, and then you have to keep making decisions.

[00:02:45]Unless you have a really good memory, which I do not, teaching staff can attest to that, then an easy way to do it is to leave bread crumbs behind, say, this is the last way I went from this node, so that when I reach a deadend, I have to turn around and backtrack.

[00:03:02]I reach a breadcrumb that say, oh, last time you went this way, next time you should go this way, and in particular, keep track at each node, which of the edges have I visited, which ones are still left to visit.

[00:03:14]And this can be done very easily on a computer using recursion.

[00:03:30]So high-level description is we're going to just recursively explore the graph, backtracking as necessary, kind of like how you solve a maze.

[00:03:54]In fact, when I was seven years old, one of the first computer programs I wrote was for solving a maze.

[00:04:01]I didn't know it was depth-first search at the time, but now I know.

[00:04:11]It was so much harder doing algorithms when I didn't know what they were.

[00:04:15]Anyway, I'm going to write some code for depth-first search, it is super simple code, the simplest graph algorithm.

[00:04:49]It's four lines.

[00:05:05]That's it.

[00:05:06]I'm going to write a little bit of code after this, but this is basic depth-first search.

[00:05:11]This will visit all the vertices reachable from a given source, vertex s.

[00:05:16]So we're given the adjacency list.

[00:05:19]I don't know why I put v here, you could erase it, it's not necessary.

[00:05:24]And all we do is, we have our vertex b, sorry, we have our vertex s.

[00:05:31]We look at all of the outgoing edges from s.

[00:05:35]For each one, we'll call it v, we check, have I visited this vertex already?

[00:05:45]A place where we need to be careful is to not repeat vertices.

[00:05:49]We need to do this in BFS as well.

[00:05:56]So, the way we're going to do that is by setting the parent of a node, we'll see what that actually means later.

[00:06:03]But for now, it's just, are you in the parent structure or not?

[00:06:05]This is initially, we've seen s, so we give it a parent of nothing, but it exists in this dictionary.

[00:06:14]If the vertex b that we're looking at is not in our dictionary, we haven't seen it yet, we mark it as seen by setting its parent to s, and then we recursively visit it.

[00:06:25]That's it.

[00:06:26]Super simple, just recurse.

[00:06:29]Sort of the magical part is the preventing yourself from repeating.

[00:06:34]As you explore the graph, if you reach something you've already seen before you just skip it again.

[00:06:39]So you only visit every vertex once, at most once.

[00:06:45]This will not visit the entire graph, it will only visit the vertices reachable from s.

[00:06:50]The next part of the code I'd like to give you is for visiting all the vertices, and in the textbook this is called the DFS, whereas this is just called DFS visit, that's sort of the recursive part, and this is sort of a top level algorithm.

[00:07:08]Here we are going to use the set of vertices, b, and here we're just going to iterate over the s's.

[00:07:47]So it looks almost the same, but what we're iterating over is different.

[00:07:52]Here we're iterating over the outgoing edges from s, here were iterating over the choices of s.

[00:08:03]So the idea here is we don't really know where to start our search.

[00:08:06]If it's a disconnected graph or not a strongly connected graph, we might have to start our search multiple times.

[00:08:12]This DFS algorithm is finding all the possible places you might start the search and trying them all.

[00:08:19]So it's like, OK, let's try the first vertex.

[00:08:21]If that hasn't been visited, which initially nothing's been visited, then visit it, recursively, everything reachable from s.

[00:08:29]Then you go on to the second vertex.

[00:08:30]Now, you may have already visited it, then you skip it.

[00:08:32]Third vertex, maybe you visited it already.

[00:08:34]Third, fourth vertex, keep going, until you find some vertex you haven't visited at all.

[00:08:39]And then you recursively visit everything reachable from it, and you repeat.

[00:08:45]This will find all the different clusters, all the different strongly connected components of your graph.

[00:08:51]Most of the work is being done by this recursion, but then there's this top level, just to make sure that all the vertices get visited.

[00:08:59]Let's do a little example, so this is super clear, and then it will also let me do something called edge classification.

[00:09:09]Once we see every edge in the graph gets visited by DFS in one way or another, and it's really helpful to think about the different ways they can be visited.

[00:09:20]So here's a graph.

[00:09:25]I think its a similar to one from last class.

[00:09:46]It's not strongly connected, I don't think, so you can't get from these vertices to c.

[00:09:53]You can get from c to everywhere, it looks like, but not strongly connected.

[00:10:00]And we're going to run DFS, and I think, basically in alphabetical order is how we're imagining-- these vertices have to be ordered somehow, we don't really care how, but for sake of example I care.

[00:10:12]So we're going to start with a, that's the first vertex in here.

[00:10:17]We're going to recursively visit everything reachable from a, so we enter here with s equals a.

[00:10:22]So I'll mark this s1, to be the first value of s at this level.

[00:10:33]So we consider-- I'm going to check the order here-- first edge we look at, there's two outgoing edges, let's say we look at this one first.

[00:10:46]We look at b, b has not been visited yet, has no parent pointer.

[00:10:50]This one has a parent pointer of 0.

[00:10:54]B we're going to give a parent pointer of a, that's here.

[00:10:59]Then we recursively visit everything for b.

[00:11:01]So we look at all the outgoing edges from b, there's only one.

[00:11:04]So we visit this edge.

[00:11:09]for b to e. e has not been visited, so we set as parent pointer to b, an now we recursively visit e.

[00:11:16]e has only one outgoing edge, so we look at it, over here to d.

[00:11:25]d has not been visited, so we set a parent pointer to e, and we look at all the outgoing edges from d.

[00:11:31]d has one outgoing edge, which is to b. b has already been visited, so we skip that one, nothing to do.

[00:11:38]That's the else case of this if, so we do nothing in the else case, we just go to the next edge.

[00:11:45]But there's no next edge for d, so we're done.

[00:11:48]So this algorithm returns to the next level up.

[00:11:52]Next level up was e, we were iterating over the outgoing edges from e.

[00:11:55]But there was only one, so we're done, so e finishes.

[00:11:59]Then we backtrack to b, which is always going back along the parent pointer, but it's also just in the recursion.

[00:12:08]We know where to go back to.

[00:12:10]We were going over the outgoing edges from b, there's only one, we're done.

[00:12:15]So we go back to a.

[00:12:16]We only looked at one outgoing edge from a.

[00:12:18]There's another outgoing edge, which is this one, but we've already visited d, so we skip over that one, too, so we're done recursively visiting everything reachable from a.

[00:12:30]Now we go back to this loop, the outer loop.

[00:12:34]So we did a, next we look at b, we say, oh b has been visited, we don't need to do anything from there.

[00:12:40]Then we go to c, c hasn't been visited so we're going to loop from c, and so this is our second choice of s in this recursion, or in this outer loop.

[00:12:53]And so we look at the outgoing edges from s2, let me match the order in the notes.

[00:12:59]Let's say first we go to f.

[00:13:03]f has not been visited, so we set its parent pointer to c.

[00:13:08]Then we look at all the outgoing edges from f.

[00:13:10]There's one outgoing edge from f, it goes to f.

[00:13:13]I guess I shouldn't really bold this, sorry.

[00:13:18]I'll say what the bold edges mean in a moment.

[00:13:23]This is just a regular edge.

[00:13:25]We follow the edge from f to f.

[00:13:27]We see, oh, f has already been visited, it already has a parent pointer, so there's no point going down there.

[00:13:33]We're done with f, that's the only outgoing edge.

[00:13:35]We go back to c, there's one other outgoing edge, but it leads to a vertex we've already visited, namely e, and so we're done with visiting everything reachable from c.

[00:13:44]We didn't visit everything reachable from c, because some of it was already visited from a.

[00:13:49]Then we go back to the outer loop, say, OK, what about d?

[00:13:51]D has been visited, what about e?

[00:13:53]E's been visited, what about f?

[00:13:54]F's been visited.

[00:13:55]So we're visiting these vertices again, but should only be twice in total, and in the end we visit all the vertices, and, in a certain sense, all the edges as well.

[00:14:12]Let's talk about running time.

[00:14:27]What do you think the running time of this algorithm is?

[00:14:38]Anyone?

[00:14:39]Time to wake up.

[00:14:42]AUDIENCE: Upper bound?

[00:14:43]PROFESSOR: Upper bound, sure.

[00:14:45]AUDIENCE: V?

[00:14:46]PROFESSOR: V?

[00:14:46]AUDIENCE: [INAUDIBLE].

[00:14:48]PROFESSOR: V is a little bit optimistic, plus e, good, collaborative effort.

[00:14:57]It's linear time, just like BFS.

[00:15:00]This is what we call linear time, because this is the size of the input.

[00:15:07]It's theta V plus E for the whole thing.

[00:15:11]The size of the input was v plus e.

[00:15:12]We needed v slots in an array, plus we needed e items in these linked lists, one for each edge.

[00:15:20]We have to traverse that whole structure.

[00:15:22]The reason it's order v plus e is-- first, as you were saying, you're visiting every vertex once in this outer loop, so not worrying about the recursion in DFS alone, so that's order b.

[00:15:48]Then have to worry about this recursion, but we know that whenever we call DFS visit on a vertex, that it did not have a parent before.

[00:15:58]Right before we called DFS visit, we set its parent for the first time.

[00:16:03]Right before we called DFS visit on v here, we set as parent for the first time, because it wasn't set before.

[00:16:09]So DFS visit, and I'm going to just write of v, meaning the last argument here.

[00:16:25]It's called once, at most once, per vertex b.

[00:16:35]But it does not take constant time.

[00:16:37]This takes constant time per vertex, plus a recursive call.

[00:16:41]This thing, this takes constant time, but there's a for loop here.

[00:16:44]We have to pay for however many outgoing edges there are from b, that's the part you're missing.

[00:16:52]And we pay length of adjacency of v for that vertex.

[00:17:00]So the total in addition to this v is going to be the order, sum overall vertices, v in capital V, of length of the adjacency, list for v, which is E. This is the handshaking lemma from last time.

[00:17:24]It's twice e for undirected graphs, it's e for directed graphs.

[00:17:29]I've drawn directed graphs here, it's a little more interesting.

[00:17:33]OK, so it's linear time, just like the BFS, so you could say, who cares, but DFS offers a lot of different properties than BFS.

[00:17:42]They each have their niche.

[00:17:44]BFS is great for shortest paths.

[00:17:46]You want to know the fastest way to solve the Rubik's cube, BFS will find it.

[00:17:50]You want to find the fastest way to solve the Rubik's cube, DFS will not find it.

[00:17:55]It's not following shortest paths here.

[00:17:57]Going from a to d, we use the path of length 3, that's the bold edges.

[00:18:01]We could have gone directly from a to d, so it's a different kind of search, but sort of the inverse.

[00:18:07]But it's extremely useful, in particular, in the way that it classifies edges.

[00:18:13]So let me talk about edge classification.

[00:18:27]You can check every edge in this graph gets visited.

[00:18:31]In a directed graph every edge gets visited once, in an undirected graph, every edge gets visited twice, once from each side.

[00:18:40]And when you visit that edge, there's sort of different categories of what could happen to it.

[00:18:45]Maybe the edge led to something unvisited, when you went there.

[00:18:50]We call those tree edges.

[00:19:10]That's what the parent pointers are specifying and all the bold edges here are called three edges.

[00:19:16]This is when we visit a new vertex via that edge.

[00:19:29]So we look at the other side of the edge, we discover a new vertex.

[00:19:33]Those are what we call tree edges, it turns out they form a tree, a directed tree.

[00:19:37]That's a lemma you can prove.

[00:19:39]You can see it here.

[00:19:40]We just have a path, actually a forest would be more accurate.

[00:19:44]We have a path abed, and we have an edge cf, but, in general, it's a forest.

[00:19:51]So for example, if there was another thing coming from e here, let's modify my graph, we would, at some point, visit that edge and say, oh, here's a new way to go, and now that bold structure forms an actual tree.

[00:20:04]These are called tree edges, you can call them forest edges if you feel like it.

[00:20:10]There are other edges in there, the nonbold edges, and the textbook distinguishes three types, three types?

[00:20:17]Three types, so many types.

[00:20:22]They are forward edges, backward edges, and cross edges.

[00:20:44]Some of these are more useful to distinguish than others, but it doesn't hurt to have them all.

[00:20:51]So, for example, this edge I'm going to call a forward edge, just write f, that's unambiguous, because it goes, in some sense, forward along the tree.

[00:21:04]It goes from the root of this tree to a descendant.

[00:21:09]There is a path in the tree from a to d, so we call it a forward edge.

[00:21:14]By contrast, this edge I'm going to call a backward edge, because it goes from a node in the tree to an ancestor in the trees.

[00:21:26]If you think of parents, I can go from d to its parent to its parent, and that's where the edge goes, so that's a backward edge-- double check I got these not reversed, yeah, that's right.

[00:21:36]Forward edge because I could go from d to its parent to its parent to its parent and the edge went the other way, that's a forward edge.

[00:21:44]So forward edge goes from a node to a descendant in the tree.

[00:21:52]Backward edge goes from a node to an ancestor in the tree.

[00:22:02]And when I say, tree, I mean forest.

[00:22:07]And then all the other edges are cross edges.

[00:22:12]So I guess, here, this is a cross edge.

[00:22:17]In this case, it goes from one tree to another, doesn't have to go between different trees.

[00:22:22]For example, let's say I'm visiting d, then I go back to e, I visit g, or there could be this edge.

[00:22:32]If this edge existed, it would be a cross edge, because g and d are not ancestor related, neither one is an ancestor of the other, they are siblings actually.

[00:22:46]So there's, in general, there's going to be some subtree over here, some subtree over here, and this is a cross edge between two different subtrees.

[00:22:55]This cross edge is between two, sort of, non ancestor related, I think is the shortest way to write this, subtrees or nodes.

[00:23:26]A little puzzle for you, well, I guess the first question is, how do you compute this structure?

[00:23:31]How do you compute which edges are which?

[00:23:34]This is not hard, although I haven't written it in the code here.

[00:23:37]You can check the textbook for one way to do it.

[00:23:42]The parent structure tells you which edges are tree edges.

[00:23:45]So that part we have done.

[00:23:47]Every parent pointer corresponds to the reverse of a tree edge, so at the same time you could mark that edge a tree edge, and you'd know which edges are tree edges and which edges are nontree edges.

[00:23:58]If you want to know which are forward, which are backward, which are cross edges, the key thing you need to know is, well, in particular, for backward edges, one way to compute them is to mark which nodes you are currently exploring.

[00:24:19]So when we do a DFS visit on a node, we could say at the beginning here, basically, we're starting to visit s, say, start s, and then at the end of this for loop, we write, we're finished with s.

[00:24:38]And you could mark that in the s structure.

[00:24:40]You could say s dot in process is true up here, s dot in process equals false down here.

[00:24:46]Keep track of which nodes are currently in the recursion stack, just by marking them and unmarking them at the beginning and the end.

[00:24:55]Then we'll know, if we follow an edge and it's an edge to somebody who's already in the stack, then it's a backward edge, because that's-- everyone in the stack is an ancestor from our current node.

[00:25:10]Detecting forward edges, it's a little trickier.

[00:25:18]Forward edges versus cross edges, any suggestions on an easy way to do that?

[00:25:28]I don't think I know an easy way to do that.

[00:25:31]It can be done.

[00:25:33]The way the textbook does it is a little bit more sophisticated, in that when they start visiting a vertex, they record the time that it got visited.

[00:25:44]What's time?

[00:25:46]You could think of it as the clock on your computer, another way to do it is, every time you do a step in this algorithm, you increment a counter.

[00:25:55]So every time anything happens, you increment a counter, and then you store the value of that counter here for s, that would be the start time for s, you store the finish time for s down here, and then this gives you, this tells you when a node was visited, and you can use that to compute when an edge is a forward edge and otherwise it's a cross edge.

[00:26:14]It's not terribly exciting, though, so I'm not going to detail that.

[00:26:18]You can look at the textbook if you're interested.

[00:26:22]But here's a fun puzzle.

[00:26:24]In an undirected graph, which of these edges can exist?

[00:26:32]We can have a vote, do some democratic mathematics.

[00:26:38]How many people think tree edges exist in undirected graphs?

[00:26:44]You, OK.

[00:26:46]Sarini does.

[00:26:46]That's a good sign.

[00:26:47]How many people think forward edges exist in an undirected graph?

[00:26:54]A couple.

[00:26:54]How many people think backward edges exist in an undirected graph?

[00:26:59]Couple.

[00:27:00]How many people think cross edges exist in undirected graph?

[00:27:03]More people, OK.

[00:27:05]I think voting worked.

[00:27:07]They all exist, no, that's not true.

[00:27:10]This one can exist and this one can exist.

[00:27:13]I actually wrote the wrong ones in my notes, so it's good to trick you, no, it's I made a mistake.

[00:27:19]It's very easy to get these mixed up and you can think about why this is true, maybe I'll draw some pictures to clarify.

[00:27:30]This is something, you remember the-- there was BFS diagram, I talked a little bit about this last class.

[00:27:38]Tree edges better exist, those are the things you use to visit new vertices.

[00:27:42]So that always happens, undirected or otherwise.

[00:27:45]Forward edges, though, forward edge of would be, OK, I visited this, then I visited this.

[00:27:51]Those were tree edges.

[00:27:55]Then I backtrack and I follow an edge like this.

[00:27:58]This would be a forward edge.

[00:27:59]And in a directed graph that can happen.

[00:28:03]In an undirected graph, it can also happen, right?

[00:28:11]Oh, no, it can't, it can't.

[00:28:12]OK.

[00:28:14]So confusing.

[00:28:15]undirected graph, if you look like this, you start-- let's say this is s.

[00:28:20]You start here, and suppose we follow this edge.

[00:28:24]We get to here, then we follow this edge, we get to here.

[00:28:27]Then we will follow this edge in the other direction, and that's guaranteed to finish before we get back to s.

[00:28:35]So, in order to be a forward edge, this one has to be visited after this one, from s, but in this scenario, if you follow this one first, you'll eventually get to this vertex and then you will come back, and then that will be classified as a backward edge in an undirected graph.

[00:28:49]So you can never have forward edges in an undirected graph.

[00:29:00]But I have a backward edge here, that would suggest I can have backward edges here, and no cross edges.

[00:29:08]Well, democracy did not work, I was swayed by the popular vote.

[00:29:14]So I claim, apparently, cross edges do not exist.

[00:29:17]Let's try to draw this.

[00:29:18]So a cross edge typical scenario would be either here, you follow this edge, you backtrack, you follow another edge, and then you discover there's was an edge back to some other subtree that you've already visited.

[00:29:36]That can happen in an undirected graph.

[00:29:38]For the same reason, if I follow this one first, and this edge exists undirected, then I will go down that way.

[00:29:46]So it will be actually tree edge, not a cross edge.

[00:29:50]OK, phew.

[00:29:51]That means my notes were correct.

[00:29:56]I was surprised, because they were copied from the textbook, uncorrect my correction.

[00:30:04]Good.

[00:30:10]So what?

[00:30:13]Why do I care about these edge classifications?

[00:30:15]I claim they're super handy for two problems, cycle detection, which is pretty intuitive problem.

[00:30:24]Does my graph have any cycles?

[00:30:26]In the directed case, this is particularly interesting.

[00:30:29]I want to know, does a graph have any directed cycles?

[00:30:33]And another problem called topological sort, which we will get to.

[00:30:41]So let's start with cycle detection.

[00:30:45]This is actually a warmup for topological sort.

[00:30:52]So does my graph have any cycles?

[00:30:55]G has a cycle, I claim.

[00:31:00]This happens, if and only if, G has a back edge, or let's say, a depth-first search of that graph has a back edge.

[00:31:17]So it doesn't matter where I start from or how this algorithm-- I run this top level DFS algorithm, explore the whole graph, because I want to know in the whole graph is there a cycle?

[00:31:26]I claim, if there's a back edge, then there's a cycle.

[00:31:33]So it all comes down to back edges.

[00:31:35]This will work for both directed and undirected graphs.

[00:31:38]Detecting cycles is pretty easy in undirected graphs.

[00:31:41]It's a little more subtle with directed graphs, because you have to worry about the edge directions.

[00:31:46]So let's prove this.

[00:31:49]We haven't done a serious proof in a while, so this is still a pretty easy one, let's think about it.

[00:31:57]What do you think is the easier direction to prove here, left or right?

[00:32:02]To more democracy.

[00:32:03]How many people think left is easy?

[00:32:07]A couple.

[00:32:08]How many people think right is easy?

[00:32:10]A whole bunch more.

[00:32:12]I disagree with you.

[00:32:14]I guess it depends what you consider easy.

[00:32:18]Let me show you how easy left is.

[00:32:21]Left is, I have a back edge, I want to claim there's a cycle.

[00:32:25]What is the back edge look like?

[00:32:27]Well, it's an edge to an ancestor in the tree.

[00:32:34]If this node is a descendant of this node and this node is an ancestor of this node, that's saying there are tree edges, there's a path, a tree path, that connects one to the other.

[00:32:49]So these are tree edges, because this is supposed to be an ancestor, and this is supposed to be a descendant.

[00:33:03]And that's the definition of a back edge.

[00:33:08]Do you see a cycle?

[00:33:11]I see a cycle.

[00:33:12]This is a cycle, directed cycle.

[00:33:17]So if there's a back edge, by definition, it makes a cycle.

[00:33:21]Now, it's harder to say if I have 10 back edges, how many cycles are there?

[00:33:25]Could be many.

[00:33:26]But if there's a back edge, there's definitely at least one cycle.

[00:33:34]The other direction is also not too hard, but I would hesitate to call it easy.

[00:33:38]Any suggestions if, I know there is a cycle, how do I prove that there's a back edge somewhere?

[00:33:46]Think about that, let me draw a cycle.

[00:34:11]There's a length k cycle.

[00:34:16]Where do you think, which of these edges do you think is going to be a back edge?

[00:34:19]Let's hope it's one of these edges.

[00:34:23]Sorry?

[00:34:24]AUDIENCE: Vk to v zero.

[00:34:25]PROFESSOR: Vk to v zero.

[00:34:26]That's a good idea, maybe this is a back edge.

[00:34:31]Of course, this is symmetric, why that edge?

[00:34:34]I labeled it in a suggestive way, but I need to say something before I know actually which edge is going to be the back edge.

[00:34:42]AUDIENCE: You have to say you start to v zero?

[00:34:44]PROFESSOR: Start at v zero.

[00:34:45]If I started a search of v zero, that looks good, because the search is kind of going to go in this direction.

[00:34:51]vk will maybe be the last thing to be visited, that's not actually true.

[00:34:55]Could be there's an edge directly from v zero to vk, but intuitively vk will kind of later, and then when this edge gets visited, this will be an ancestor and it will be a back edge.

[00:35:05]Of course, we may not start a search here, so calling it the start of the search is not quite right, a little different.

[00:35:16]AUDIENCE: First vertex that gets hit [INAUDIBLE].

[00:35:18]PROFESSOR: First vertex that gets hit, good.

[00:35:21]I'm going to start the numbering, v zero, let's assume v 0 is the first vertex in the cycle, visited by the depth-first search.

[00:35:47]Together, if you want some pillows if you like them, especially convenient that they're in front.

[00:35:56]So right, if it's not v zero, say v3 was the first one visited.

[00:36:00]We will just change the labeling, so that's v zero, that's v1, that's v, and so on.

[00:36:06]So set this labeling, so that v0 first one, first vertex that gets visited.

[00:36:12]Then, I claim that-- let me just write the claim first.

[00:36:20]This edge vkv0 will be a back edge.

[00:36:26]We'll just say, is back edge.

[00:36:29]And I would say this is not obvious, be a little careful.

[00:36:50]We have to somehow exploit the depth-first nature of DFS, the fact that it goes deep-- it goes as deep as it can before backtracking.

[00:37:00]If you think about it, we're starting, at this point we are starting a search relative to this cycle.

[00:37:05]No one has been visited, except v zero just got visited, has a parent pointer off somewhere else.

[00:37:15]What do we do next?

[00:37:16]Well, we visit all the outgoing edges from v zero, there might be many of them. it could be edge from v zero to v1, it could an edge from v zero to v3, it could be an edge from v zero to something else.

[00:37:28]We don't know which one's going to happen first.

[00:37:31]But the one thing I can claim is that v1 will be visited before we finish visiting v zero.

[00:37:52]From v zero, we might go somewhere else, we might go somewhere else that might eventually lead to v1 by some other route, but in particular, we look at that edge from v zero to v1.

[00:38:01]And so, at some point, we're searching, we're visiting all the things reachable from v zero, that includes v1, and that will happen, we will touch v1 for the first time, because it hasn't been touched yet.

[00:38:13]We will visit it before we finish visiting v zero.

[00:38:17]The same goes actually for all of v i's, because they're all reachable from v zero.

[00:38:23]You can prove this by induction.

[00:38:25]You'll have to visit v1 before you finish visiting v zero.

[00:38:29]You'll have to visit v2 before you finish visiting v1, although you might actually visit v2 before v1.

[00:38:35]You would definitely finish, you'll finished v2 before you finish v1, and so on.

[00:38:41]So vi will be visited before you finish vi minus 1, but in particular, what we care about is that vk is visited before we finish v zero.

[00:39:02]And it will be entirely visited.

[00:39:03]We will finish visiting vk before we finish visiting v zero.

[00:39:07]We will start decay vk after we start to v zero, because v zero is first.

[00:39:12]So the order is going to look like, start v zero, at some point we will start vk.

[00:39:20]Then we'll finish vk, then we'll finish v zero.

[00:39:27]This is something the textbook likes to call, and I like to call, balanced parentheses.

[00:39:33]You can think of it as, we start v zero, then we start vk, then we finish vk, then we finish v zero.

[00:39:42]And these match up and their balanced.

[00:39:46]Depth-first search always looks like that, because once you start a vertex, you keep chugging until you visited all the things reachable from it.

[00:39:54]Then you finish it.

[00:39:55]You won't finish v zero before you finish vk, because it's part of the recursion.

[00:40:00]You can't return at a higher level before you return at the lower levels.

[00:40:04]So we've just argued that the order is like this, because v zero was first, so vk starts after v zero, and also we're going to finish vk before we finish v zero, because it's reachable, and hasn't been visited before.

[00:40:17]So, in here, we consider vkv zero.

[00:40:28]When we consider that edge, it will be a back edge.

[00:40:34]Why?

[00:40:35]Because v zero is currently on the recursion stack, and so you will have marked v zero as currently in process.

[00:40:42]So when you look at that edge, you see it's a back edge, it's an edge to your ancestor.

[00:40:47]That's the proof.

[00:40:51]Any questions about that?

[00:40:55]It's pretty easy once you set up the starting point, which is look at the first time you visit the cycle, than just think about how you walk around the cycle.

[00:41:03]There's lots of ways you might walk around the cycle, but it's guaranteed you'll visit vk at some point, then you'll look at the edge. v0 is still in the stack, so it's a back edge.

[00:41:12]And so this proves that having a cycle is equivalent to having a back edge.

[00:41:16]This gives you an easy linear time algorithm to tell, does my graph have a cycle?

[00:41:20]And if it does, it's actually easy to find one, because we find a back edge, just follow the tree edges, and you get your cycle.

[00:41:29]So if someone gives you a graph and say, hey, I think this is acyclic, you can very quickly say, no, it's not, here's a cycle, or say, yeah, I agree, no back edges, I only have tree, forward, and cross edges.

[00:41:49]OK, that was application 1.

[00:41:56]Application 2 is topological sort, which we're going to think about in the setting of a problem called job scheduling.

[00:42:07]So job scheduling, we are given a directed acyclic graph.

[00:42:21]I want to order the vertices so that all edges point from lower order to high order.

[00:42:52]Directed acyclic graph is called a DAG, you should know that from 042.

[00:42:59]And maybe I'll draw one for kicks.

[00:43:32]Now, I've drawn the graph so all the edges go left to right, so you can see that there's no cycles here, but generally you'd run DFS and you'd detect there's no cycles.

[00:43:41]And now, imagine these vertices represent things you need to do.

[00:43:45]The textbook has a funny example where you're getting dressed, so you have these constraints that say, well, I've got to put my socks on before put my shoes on.

[00:43:53]And then I've got to put my underwear on before I put my pants on, and all these kinds of things.

[00:43:59]You would code that as a directed acyclic graph.

[00:44:01]You hope there's no cycles, because then you can't get dressed.

[00:44:05]And there's some things, like, well, I could put my glasses on whenever, although actually I should put my glasses on before I do anything else, otherwise there's problems.

[00:44:12]I don't know, you could put your watch on at any time, unless you need to know what time is.

[00:44:17]So there's some disconnected parts, whatever.

[00:44:20]There's some unrelated things, like, I don't care the order between my shirt and my pants or whatever, some things aren't constrained.

[00:44:28]What you'd like to do is choose an actual order to do things.

[00:44:31]Say you're a sequential being, you can only do one thing at a time, so I want to compute a total order.

[00:44:37]First I'll do g, then I'll do a, then I can do h, because I've done both of the predecessors.

[00:44:42]Then I can't do be, because I haven't done d, so maybe I'll do d first, and then b, and than e, then c, then f, then i.

[00:44:50]That would be a valid order, because all edges point from an earlier number to a later number.

[00:44:55]So that's the goal.

[00:44:56]And these are real job scheduling problems that come up, you'll see more applications in your problem set.

[00:45:04]How do we do this?

[00:45:07]Well, at this point we have two algorithms, and I pretty much revealed it is DFS.

[00:45:10]DFS will do this.

[00:45:13]It's a topological sort, is what this algorithm is usually called.

[00:45:20]Topological sort because you're given a graph, which you could think of as a topology.

[00:45:25]You want to sort it, in a certain sense.

[00:45:26]It's not like sorting numbers, it's sorting vertices in a graph, so, hence, topological sort.

[00:45:32]That's the name of the algorithm.

[00:45:34]And it's run DFS, and output the reverse of the finishing times of vertices.

[00:45:55]so this is another application where you really want to visit all the vertices in the graph, so we use this top level DFS, so everybody gets visited.

[00:46:05]And there are these finishing times, so every time I finish a vertex, I could add it to a list.

[00:46:11]Say OK, that one was finished next, than this one is finished, than this one's finished.

[00:46:15]I take that order and I reverse it.

[00:46:18]That will be a topological order.

[00:46:21]Why?

[00:46:22]Who knows.

[00:46:24]Let's prove it.

[00:46:34]We've actually done pretty much the hard work, which is to say-- we're assuming our graph has no cycles, so that tells us by this cycle detection that there are no back edges.

[00:46:47]Back edges are kind of the annoying part.

[00:46:49]Now they don't exist here.

[00:46:51]So all the edges are tree edges, forward edges, and cross edges, and we use that to prove the theorem.

[00:47:05]So we want to prove that all the edges point from an earlier number to a later number.

[00:47:15]So what that means is for an edge, uv, we want to show that v finishes before u.

[00:47:32]That's the reverse, because what we're taking is the reverse of the finishing order.

[00:47:38]So edge uv, I want to make sure v finishes first, so that u will be ordered first.

[00:47:45]Well, there are two cases.

[00:47:51]Case 1 is that u starts before v. Case 2 is that he v before u.

[00:48:06]At some point they start, because we visit the whole graph.

[00:48:13]This top loop guarantees that.

[00:48:16]So consider what order we visit them first, at the beginning, and then we'll think about how they finish.

[00:48:23]Well, this case is kind of something we've seen before.

[00:48:27]We visit u, we have not yet visited v, but v is reachable from u, so maybe via this edge, or maybe via some other path, we will eventually visit v in the recursion for u.

[00:48:41]So before u finishes, we will visit v, visit v before u finishes.

[00:48:53]That sentence is just like this sentence, so same kind of argument.

[00:48:59]We won't go into detail, because we already did that several times.

[00:49:04]So that means we'll visit v, we will completely visit v, we will finish v before we finish u and that's what we wanted to prove.

[00:49:12]So in that case is good.

[00:49:14]The other cases is that v starts before u.

[00:49:18]Here, you might get slightly worried.

[00:49:21]So we have an edge, uv, still, same direction.

[00:49:24]But now we start at v, u has not yet been visited.

[00:49:29]Well, now we worry that we visit u.

[00:49:35]If we visit u, we're going to finish u before we finish v, but we want it to be the other way around.

[00:49:40]Why can't that happen?

[00:49:43]AUDIENCE: [INAUDIBLE].

[00:49:44]PROFESSOR: Because there's a back edge somewhere here.

[00:49:46]In particular, the graph would have to be cyclic.

[00:49:48]This is a cycle, so this can't happen, a contradiction.

[00:49:54]So v will finish before we visit u at all.

[00:50:04]So v will still finish first, because we don't even touch u, because there's no cycles.

[00:50:10]So that's actually the proof that topological sort gives you a valid job schedule, and it's kind of-- there are even more things you can do with DFS.

[00:50:21]We'll see some in recitations, more in the textbook.

[00:50:24]But simple algorithm, can do a lot of nifty things with it, very fast, linear time.