1 00:00:00,750 --> 00:00:06,600 OK, so now that we have looked at depth first search, we are going to talk about a cool application 2 00:00:06,600 --> 00:00:12,000 of depth, first search, and this isn't like a practical application that I'm talking about for a specific 3 00:00:12,450 --> 00:00:15,420 problem that you would solve or some type of project you would build. 4 00:00:16,110 --> 00:00:22,800 This is a cool algorithm that uses depth first search that can be then in turn used for all kinds of 5 00:00:22,800 --> 00:00:25,680 applications, and that is called topological sort. 6 00:00:26,490 --> 00:00:28,050 So let's get right into it. 7 00:00:29,930 --> 00:00:32,090 I have a graph right here. 8 00:00:32,330 --> 00:00:36,600 And as you can see, there's a few things that you might recognize. 9 00:00:36,620 --> 00:00:39,200 We have directed edges here. 10 00:00:39,860 --> 00:00:46,520 And if you look more closely at the graph, you will notice that not only does it have directed edges, 11 00:00:46,520 --> 00:00:49,610 but it does not have any cycles. 12 00:00:49,700 --> 00:00:55,100 So you can't go something like this, you know, from this edge to here from this vertex two, this 13 00:00:55,100 --> 00:01:00,650 vertex to this vertex back or anything that there's no loops here that you can see. 14 00:01:00,680 --> 00:01:09,200 So this is what we refer to as a DAG for short, but that is directed a cyclic graph. 15 00:01:10,250 --> 00:01:16,340 And it's actually required that we have a directed acyclic graph to perform topological sort. 16 00:01:17,760 --> 00:01:21,180 So what is topological sort? 17 00:01:21,630 --> 00:01:28,980 So it gives you a non unique and I'm stressing that because you will see that the ordering in which 18 00:01:28,980 --> 00:01:35,170 I go through this and create the type of logical wording of the graph, a type of logical ordering. 19 00:01:35,760 --> 00:01:40,140 I'm saying a liquid topological ordering because there can be multiple ordering. 20 00:01:40,350 --> 00:01:46,680 It may not be the same as what you might get if you do this problem and start somewhere else, or it 21 00:01:46,680 --> 00:01:47,760 just comes out different. 22 00:01:48,360 --> 00:01:58,890 The point of it is that you're going to visit the nodes in depth, first search fashion and the final 23 00:01:58,890 --> 00:02:02,230 ordering that you will have that you with a store in a container. 24 00:02:02,250 --> 00:02:06,030 As you will see, I'll put a container down here for the walk through that I'm going to do. 25 00:02:07,350 --> 00:02:10,850 It will not have any conflicts in that ordering. 26 00:02:10,860 --> 00:02:16,560 If you start from left and go to the right of all the labeled vertices, which I will label in a moment, 27 00:02:17,340 --> 00:02:25,380 you all of the vertices on the left, anything to the right means that that vertex to the left of it 28 00:02:26,190 --> 00:02:31,500 basically has a directional edge going out to that direction. 29 00:02:31,500 --> 00:02:32,460 So you could not. 30 00:02:32,670 --> 00:02:37,620 You can go from left to right, but you couldn't traverse from right to left on those. 31 00:02:37,800 --> 00:02:45,360 So it's basically the idea that you have to come from somewhere to get to a specific node and topological 32 00:02:45,360 --> 00:02:52,740 sort ensures that it produces an ordering where you couldn't have something like, you know, you start 33 00:02:52,740 --> 00:02:59,610 with this node and then afterwards, you know you, you visit this node, you can't visit this node 34 00:02:59,610 --> 00:03:06,060 right here and tell this nodes are already visited because you notice that it basically you have to 35 00:03:06,060 --> 00:03:07,770 come from this node to get to here. 36 00:03:07,770 --> 00:03:10,500 You have to go from this node to this node to this node. 37 00:03:10,500 --> 00:03:12,030 You can't let go here. 38 00:03:13,110 --> 00:03:16,620 And visit this first without this already being visited. 39 00:03:16,830 --> 00:03:22,560 And that's what topological sort will ensure that we have an ordering that respects rules like that. 40 00:03:25,280 --> 00:03:31,130 So let's go ahead and walk through an example this time, I'm not going to have a stack over here, 41 00:03:31,130 --> 00:03:36,620 but I'm going to have a little marker, a little smiley face that represents our stack and then we will 42 00:03:36,620 --> 00:03:37,730 mark our visited nodes. 43 00:03:38,090 --> 00:03:45,560 And down here on the bottom, I will build a topological ordering so you can think of it as like a container 44 00:03:46,580 --> 00:03:49,220 that we're adding our topological ordering to. 45 00:03:49,700 --> 00:03:58,160 And an important point is that I will be adding these vertices in reverse order and I will be adding 46 00:03:58,160 --> 00:04:01,310 the vertices in the recursive process of the depth first search. 47 00:04:02,270 --> 00:04:10,220 So it is a very simple algorithm now that you understand depth, first search. 48 00:04:10,220 --> 00:04:18,500 So all we're really doing is we are performing depth first search multiple times, if necessary, on 49 00:04:18,500 --> 00:04:21,530 the graph until we visited all the nodes. 50 00:04:22,620 --> 00:04:30,330 And we are when we're doing the recursive process, when we're popping things off the stack, we will 51 00:04:30,330 --> 00:04:36,720 be adding them from right to left in reverse order into a container, and that's all we're really doing. 52 00:04:37,290 --> 00:04:39,750 So let's go ahead and get into it. 53 00:04:40,110 --> 00:04:44,970 I'm going to start here at Vertex A, so I have this little smiley face. 54 00:04:44,970 --> 00:04:47,170 That means we're going to add Vertex eight to the stack. 55 00:04:47,190 --> 00:04:49,500 So it's on the stack right now. 56 00:04:50,550 --> 00:04:54,030 Then I head over to see I add Vertex C to the stack. 57 00:04:54,630 --> 00:04:57,720 But you notice there is nowhere I can go from C. 58 00:04:57,720 --> 00:04:59,760 There's an incoming edge, but it doesn't go out. 59 00:04:59,760 --> 00:05:01,320 There's no other outcome in edge. 60 00:05:01,320 --> 00:05:03,210 There is no out coming edge from C. 61 00:05:03,750 --> 00:05:07,140 So because of that, we are going to pop C off the stack. 62 00:05:07,140 --> 00:05:08,460 I take the smiley face away. 63 00:05:08,460 --> 00:05:09,750 It's no longer on the stack. 64 00:05:11,410 --> 00:05:13,030 The last thing on the stack is a. 65 00:05:13,330 --> 00:05:17,830 And I'm going to add it here on the right side to my topological ordering. 66 00:05:20,200 --> 00:05:25,630 So then I can go to B from A we come back to air and we still have somewhere to go. 67 00:05:25,930 --> 00:05:27,820 I'm going to push B to the stack. 68 00:05:28,850 --> 00:05:30,920 From B. I'm going to head over to E! 69 00:05:31,070 --> 00:05:34,320 I'm going to push E to the stack from E! 70 00:05:34,340 --> 00:05:37,370 I'm going to head to G, I'm going to post G to the stack. 71 00:05:37,380 --> 00:05:40,460 So we're just doing the same depth for a search here, you know, going deep. 72 00:05:41,360 --> 00:05:42,920 I go to H. 73 00:05:43,340 --> 00:05:44,760 I push h to the stack. 74 00:05:44,780 --> 00:05:47,000 There's no outgoing edges from H. 75 00:05:47,000 --> 00:05:50,600 I cannot get to anything, so I pop it off the stack. 76 00:05:51,440 --> 00:05:54,410 Since I'm popping out of the stack, we're in our recursive process. 77 00:05:54,410 --> 00:06:00,200 I'm going to add that popped up h to my container and we're going in reverse order. 78 00:06:00,200 --> 00:06:01,850 Remember from right to left here. 79 00:06:02,240 --> 00:06:08,150 So I'm pushing it to the front, not pushing it to the back of this container from G. 80 00:06:08,150 --> 00:06:09,170 We can still go to F. 81 00:06:09,170 --> 00:06:10,280 So let's go to F. 82 00:06:10,940 --> 00:06:13,430 Let's add that to the stack from F we can go to. 83 00:06:14,090 --> 00:06:15,650 So let's add it to the stack. 84 00:06:15,920 --> 00:06:20,450 No outgoing edges from I as pop that off the stack. 85 00:06:21,690 --> 00:06:26,570 Now we're back at F well, actually first, we want to add I to our container here since we purchased 86 00:06:26,570 --> 00:06:27,060 off the stack. 87 00:06:27,240 --> 00:06:33,600 Now that we're back at F, we noticed that F has outgoing edges, but we've visited all of these vertices, 88 00:06:33,600 --> 00:06:36,990 so therefore we're going to pop f off the stack. 89 00:06:37,440 --> 00:06:44,100 So the recursive version of this, you can think of us as going back to the previous stack frame now, 90 00:06:45,270 --> 00:06:48,270 and we're going to put that in our container as well since we pop it. 91 00:06:49,200 --> 00:06:55,050 Same thing with G already visited F and H, so we're going to pop that off and put it to our container. 92 00:06:55,800 --> 00:06:56,930 Same thing with E! 93 00:06:56,940 --> 00:07:02,880 The only outgoing edge was here to G and it's been visited, so pop it off added to the container. 94 00:07:03,810 --> 00:07:09,060 Come back to be, you know, B has an outgoing edge to DX. 95 00:07:09,090 --> 00:07:12,720 So let's go explore d add to the stack. 96 00:07:13,630 --> 00:07:18,230 Can't go anywhere from DB besides this place that we've already visited here at E! 97 00:07:18,490 --> 00:07:21,970 So pop it off the stack, add it to our container. 98 00:07:23,540 --> 00:07:24,650 Come back to B. 99 00:07:25,130 --> 00:07:30,050 B, we've already visited these two outgoing adjust to these practices. 100 00:07:30,350 --> 00:07:33,200 So let's take that off the stack. 101 00:07:33,200 --> 00:07:34,280 Put it in our container. 102 00:07:34,820 --> 00:07:39,590 Go back to a and this is normally where we'd be wrapping up our depth first search. 103 00:07:40,690 --> 00:07:46,460 But for this, this is where the end of this depth, first search process would would. 104 00:07:48,140 --> 00:07:48,620 Stop. 105 00:07:48,650 --> 00:07:51,890 So we've gone all the way through and came all the way back to where we started. 106 00:07:53,100 --> 00:07:57,390 But we're actually still going to have to visit this, okay, because, you know, it's kind of like 107 00:07:57,390 --> 00:08:03,240 a initial starting node and we start here a and had no way to get to K, so we'll do the same thing. 108 00:08:03,240 --> 00:08:04,980 Pop this off the stack at it. 109 00:08:05,550 --> 00:08:07,370 And now we're going to start at K. 110 00:08:07,530 --> 00:08:13,020 So we start at K and we start the whole depth versus project process again. 111 00:08:13,200 --> 00:08:19,530 Add K to the stack, but you notice that we've already visited B and E, which are these two outgoing 112 00:08:19,530 --> 00:08:22,070 edges to these vertices from K? 113 00:08:22,590 --> 00:08:26,430 Because of that, we're actually going to immediately then pop K off the stack. 114 00:08:26,760 --> 00:08:33,210 And since we did it pop off the stack, we're going to add it to our container and now we are done and 115 00:08:33,210 --> 00:08:35,550 we have our topological ordering down here. 116 00:08:37,500 --> 00:08:44,190 And so I don't have these drawn is nodes, which if you check online, a lot of people will put, you 117 00:08:44,190 --> 00:08:49,260 know, these topological ordering as nodes and with arrows, but you can imagine it here. 118 00:08:50,680 --> 00:08:56,110 If I had circles around these, you could draw arrows kind of like this. 119 00:08:57,020 --> 00:09:05,150 As all the edges that go out to their respective nodes, like goes to be in, I could go from K to be 120 00:09:05,150 --> 00:09:08,210 like an arrow here and then K to E. 121 00:09:08,990 --> 00:09:17,300 And if I keep doing that, if I go to a and then I like draw something to see and draw something to 122 00:09:17,300 --> 00:09:17,950 be. 123 00:09:17,960 --> 00:09:22,670 And then for B, I go to D and E and so on and so forth. 124 00:09:23,420 --> 00:09:29,090 You will notice that all of the edges start from the left and go to the right. 125 00:09:29,100 --> 00:09:35,150 There are no arrows for edges that will go to the left start. 126 00:09:35,450 --> 00:09:37,820 You know, you're going to start, for example, here on H. 127 00:09:40,560 --> 00:09:42,540 And go back this direction. 128 00:09:43,770 --> 00:09:50,970 So all of the arrows, the outgoing edges will be going in the right direction, and that is actually 129 00:09:50,970 --> 00:09:55,260 a way to really show that this isn't top of logically sorted order. 130 00:09:55,620 --> 00:10:01,320 So that's a good thing to practice if you're doing some graphs on paper to better understand this. 131 00:10:02,430 --> 00:10:10,770 The main thing that we're doing with this is I am going to have a project description for you where 132 00:10:10,770 --> 00:10:20,730 you are going to take in some input and it's going to be in the form of a JSON file. 133 00:10:20,730 --> 00:10:26,760 So JavaScript object notation and I will be describing what to do for the project. 134 00:10:26,760 --> 00:10:31,650 But the goal is to use topological sort and since, you know, depth first search. 135 00:10:31,650 --> 00:10:37,740 And this is a tiny little addition on to the depth of research that you've already seen the implementation 136 00:10:37,740 --> 00:10:43,980 for, it should be pretty easy for you to modify it and create this topological sort. 137 00:10:44,430 --> 00:10:50,880 As we said, we're just performing death for search, you know, multiple times if necessary and in 138 00:10:50,880 --> 00:10:53,550 the recursive phase when we're popping off. 139 00:10:54,940 --> 00:11:00,610 From the stack, we are adding in reverse order to a container, so that's the only difference. 140 00:11:00,610 --> 00:11:03,360 I believe it is easily achievable for you. 141 00:11:03,370 --> 00:11:07,420 So we are going over this concept for you to implement it in a project. 142 00:11:09,100 --> 00:11:11,260 So what is this useful for? 143 00:11:11,290 --> 00:11:18,070 Well, one of the biggest things is build dependencies for code, because we just talked about the fact 144 00:11:18,220 --> 00:11:25,630 that the topological ordering is from the, you know, coming from Vertex that were dependencies for 145 00:11:25,630 --> 00:11:26,790 the vertex that you're at. 146 00:11:26,800 --> 00:11:32,980 So if you have some specific vertex, you must have had to come from certain ones unless it's an originating 147 00:11:32,980 --> 00:11:33,640 vertex. 148 00:11:34,420 --> 00:11:42,040 That way, the ordering basically is going to be based on those dependencies, those outgoing directed 149 00:11:42,040 --> 00:11:42,610 edges. 150 00:11:43,060 --> 00:11:48,490 So you can do the same thing for build dependencies for a code like if you need to build the code, 151 00:11:48,490 --> 00:11:54,340 compile the code, but it needs it's dependent on certain libraries and things like that. 152 00:11:55,750 --> 00:12:00,160 You know, that's a situation where topological sort could come in handy. 153 00:12:00,880 --> 00:12:06,400 Also, scheduling jobs, you know, just scheduling tasks and things like that. 154 00:12:06,760 --> 00:12:13,750 And even shortest path finding which you modify this topological saw algorithm a little bit. 155 00:12:13,750 --> 00:12:20,380 Add some extra stuff and you can find the shortest path through one of these directed acyclic graphs 156 00:12:21,220 --> 00:12:26,680 where you might have like weights on the graph, like numbers associated with it based on distances 157 00:12:26,680 --> 00:12:27,640 and things like that. 158 00:12:28,450 --> 00:12:32,440 So we won't be covering that, but definitely useful to look it up. 159 00:12:32,440 --> 00:12:38,080 Once you've done this, I believe it would be an easy addition for you to do a shortest path finding 160 00:12:38,510 --> 00:12:39,610 thing with your code. 161 00:12:41,030 --> 00:12:46,910 And of course, there is even more stuff that you can use it for just because of the useful nature. 162 00:12:48,570 --> 00:12:54,210 The time complexity is big, though, of the number of vertices plus the number of edges. 163 00:12:55,290 --> 00:13:00,960 This is because the graph edges are directed and you're only going to end up looking at each edge in 164 00:13:00,960 --> 00:13:06,750 each vertex once, even though once you implement the code, you might be like, Hey, it kind of looks 165 00:13:06,750 --> 00:13:12,390 like I have a loop and then I have like another loop inside of it, kind of, you know? 166 00:13:13,230 --> 00:13:18,360 So you might be thinking, Oh, this is going to be, you know, something squared or you're going to 167 00:13:18,360 --> 00:13:21,420 multiply vertices times, edges or something like that. 168 00:13:22,470 --> 00:13:29,880 But in fact, the time complexity should be vertices plus edges if it's implemented in a good way. 169 00:13:32,010 --> 00:13:41,580 So with that, I will leave you to the project, I will be putting in a description and I will be going 170 00:13:41,580 --> 00:13:46,860 over an implementation of the project the way that I implemented it. 171 00:13:48,120 --> 00:13:52,530 So it's kind of a walk through in case you struggled with it. 172 00:13:52,950 --> 00:13:59,700 I go through and explain everything, but before you look at that, definitely attempt the project on 173 00:13:59,700 --> 00:14:00,410 your own. 174 00:14:00,420 --> 00:14:06,570 That is the goal for you to figure stuff out and become a better programmer and understand how to put 175 00:14:06,570 --> 00:14:07,950 these algorithms to use. 176 00:14:09,170 --> 00:14:12,560 So with that, I will see you in the next lecture.