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.

