1 00:00:00,210 --> 00:00:00,930 Hi, everyone. 2 00:00:00,960 --> 00:00:06,270 So in this video, we are going to write the code for topological sword, so the return type will be 3 00:00:06,270 --> 00:00:06,660 void. 4 00:00:07,170 --> 00:00:12,270 We will be just printing the order and then let's say the name of the function is topological. 5 00:00:12,270 --> 00:00:12,840 Certainly. 6 00:00:16,830 --> 00:00:18,810 It will take Gadhafi's and input. 7 00:00:20,700 --> 00:00:26,100 So what is the first step that we need to do, the first step is basically like it depends how you have 8 00:00:26,100 --> 00:00:26,850 implemented it. 9 00:00:26,890 --> 00:00:31,980 If you can implement my ideas and say metrics or you can implement a graph or a list, so what are you 10 00:00:32,009 --> 00:00:32,369 to do? 11 00:00:32,590 --> 00:00:41,160 You need to treat, you know, to trade audio graph basically uninterrupted or all the witnesses I read 12 00:00:41,160 --> 00:00:44,880 or whatever it is and what you need to do. 13 00:00:45,120 --> 00:00:52,560 The first step is basically you need to fill this in degree at a lightweight over vertices and you need 14 00:00:52,560 --> 00:00:54,290 to fill the value of integrity degree. 15 00:00:54,300 --> 00:00:54,700 Right. 16 00:00:55,140 --> 00:01:00,030 So first of all, we need to populate this integrity and that we can easily do. 17 00:01:00,270 --> 00:01:07,220 You just need to it or whatever it is and just start filling, start filling this very simple. 18 00:01:07,230 --> 00:01:11,400 Right now, the next step, what you need to do, you will iterate. 19 00:01:13,810 --> 00:01:16,480 You will iterate over this in degree at. 20 00:01:18,640 --> 00:01:25,300 You will outrage over this integrity and what you are going to do is you will push all the vertex in 21 00:01:25,300 --> 00:01:26,770 the queue, which are independent. 22 00:01:28,210 --> 00:01:33,670 Right, so if the integrity 23 00:01:36,490 --> 00:01:41,560 for a Vortex V is basically zero, that means this node is independent. 24 00:01:42,160 --> 00:01:45,520 If it is independent, it has to be present in the queue. 25 00:01:46,030 --> 00:01:47,960 So could not push this vertex. 26 00:01:49,330 --> 00:02:00,100 And here you need to create one queue which will store Vertex after this is done, what we need to do 27 00:02:01,090 --> 00:02:02,850 while the queue is not empty. 28 00:02:03,340 --> 00:02:06,640 So while my queue is not empty. 29 00:02:11,270 --> 00:02:13,580 While my view is not empty, what do you need to do? 30 00:02:14,480 --> 00:02:16,310 You need to pick the value from the queue. 31 00:02:16,860 --> 00:02:20,000 So let's say you so what is you? 32 00:02:20,000 --> 00:02:24,770 You is basically to stop and remove this value from the queue. 33 00:02:24,770 --> 00:02:25,810 So called ARTPOP. 34 00:02:27,740 --> 00:02:29,650 Sorry, it will not be to the top. 35 00:02:29,660 --> 00:02:33,530 Actually it will be good old friend and stack we have to keep in queue. 36 00:02:33,540 --> 00:02:36,290 We have friend so this will be good. 37 00:02:36,290 --> 00:02:36,830 Our friend. 38 00:02:38,800 --> 00:02:40,430 And then culotte pop, simple. 39 00:02:40,780 --> 00:02:43,710 So for this vertex, what is the next step? 40 00:02:43,900 --> 00:02:52,630 Next step is basically go to all other neighbors, go to all the neighbors, so go to all neighbors. 41 00:02:56,630 --> 00:03:04,670 Go to all neighbors, let's say all neighbor vortex, we what we need to do, you need to reduce there 42 00:03:04,670 --> 00:03:06,530 in degree by one. 43 00:03:08,030 --> 00:03:15,350 So you need to reduce in degree of violence or any degree of B minus minus simple. 44 00:03:16,070 --> 00:03:24,090 I'm repeating myself after popping the N word to go to all the neighbors and reduce their degree by 45 00:03:24,090 --> 00:03:35,510 even so in degree of minus minus and and and end after reducing the degree by one if the degree. 46 00:03:38,220 --> 00:03:44,200 If the degree for this vertex becomes zero, that means this vertex is now independent. 47 00:03:44,580 --> 00:03:49,520 If this vertex has now become independent, then it should be part of. 48 00:03:49,530 --> 00:03:51,900 Q So we will push in the queue. 49 00:03:53,250 --> 00:03:54,000 Simple, right? 50 00:03:54,450 --> 00:03:57,710 One thing that we forgot to miss here is we forgot to print. 51 00:03:58,290 --> 00:04:02,670 So after getting Vertex, you you need to print also. 52 00:04:02,670 --> 00:04:03,060 Right. 53 00:04:03,270 --> 00:04:04,680 That was the whole team. 54 00:04:05,040 --> 00:04:12,300 So see out your vertex you and that's all you need to do that it. 55 00:04:13,540 --> 00:04:13,940 Right. 56 00:04:14,220 --> 00:04:15,530 So I'm repeating myself. 57 00:04:15,540 --> 00:04:21,209 You will take a graph as input then the first thing is basically to fill this A.R.T. how are you going 58 00:04:21,209 --> 00:04:22,140 to fill this area. 59 00:04:22,170 --> 00:04:28,020 You can just iterate over the edges or vertices basically depending upon how you are implementing your 60 00:04:28,020 --> 00:04:34,950 graph, and then you can populate this integrity after creating the integrity, create 22, iterate 61 00:04:34,950 --> 00:04:36,890 over the integrity area that you have created. 62 00:04:37,110 --> 00:04:40,660 If it is independent, if anything that is independent. 63 00:04:40,680 --> 00:04:41,950 That has to be the part of. 64 00:04:41,950 --> 00:04:45,930 Q So you will push inside the queue while the Q is not empty. 65 00:04:46,590 --> 00:04:50,580 The first element of the element on the Q and print that element. 66 00:04:51,510 --> 00:04:52,500 Print that element. 67 00:04:52,500 --> 00:04:56,870 Right, because we need to print the order, we need to print the order. 68 00:04:56,880 --> 00:05:02,730 So we need to print here then we're going to do since we have completed the task, we have enrolled 69 00:05:02,730 --> 00:05:05,080 in this course, we have completed this course. 70 00:05:05,340 --> 00:05:12,570 So what I will do, I will go to the rest of the courses, so I will go to all my neighbors and I will 71 00:05:12,570 --> 00:05:14,670 reduce their integrity by one. 72 00:05:15,750 --> 00:05:22,680 Now, after reducing the degree by one degree minus minus, it might be possible that the cause has 73 00:05:22,680 --> 00:05:24,080 now become independent. 74 00:05:24,330 --> 00:05:24,770 Right. 75 00:05:25,020 --> 00:05:32,340 So if for that cause now the end degree becomes zero, that means the cost can be enrolled and completed 76 00:05:32,340 --> 00:05:32,700 now. 77 00:05:32,910 --> 00:05:34,380 So we will push in the queue. 78 00:05:34,620 --> 00:05:39,090 We will push the course in the queue so that we can enroll in that course and complete that course. 79 00:05:39,480 --> 00:05:41,190 And there is already enough to do that. 80 00:05:41,190 --> 00:05:42,980 Is all about topological thought. 81 00:05:43,140 --> 00:05:48,780 You can implement this code in any language and if you face problem in implementing this code, then 82 00:05:48,780 --> 00:05:49,530 do let me know. 83 00:05:49,530 --> 00:05:50,700 I will provide you the code. 84 00:05:50,790 --> 00:05:53,760 So that is all about topological sorting. 85 00:05:54,240 --> 00:05:54,690 Right. 86 00:05:55,560 --> 00:05:57,180 So this is it from this video. 87 00:05:57,180 --> 00:05:59,120 Guys, I will see you in the next one. 88 00:05:59,220 --> 00:05:59,820 Thank you.